#765. [CSP-S2019 江西] 散步

[CSP-S2019 江西] 散步

题目背景

JXCSP-S T4

题目描述

公园内有 nn 个人正在散步,随着天色渐晚,所有人准备回家离开公园。公园的结构是一个首尾相连的环形图,它共有 mm 个出口,为了方便叙述,我们将人从 1n1\sim n 编号,将出口按逆时针顺序从 1m1\sim m 编号。

公园总长 LL 米,我们令 11 号出口所在的位置为 00 米,则 编号为 i(2im)i(2\le i\le m) 的出口在 11 号出口逆时针方向 aia_i 米的位置上,其中 aia_i 严格递增 ,即 i(1i<m)i(1\le i < m) 号出口与 i+1i+1 号出口相邻,由于公园是环形图,故 mm 号出口与 11 号出口也相邻。每个出口还有一个通行限制 lil_i,表示最多有 lil_i 个人能从 ii 号出口离开。

所有人回家时将按自己的朝向,可能是顺时针方向,也可能是逆时针方向不断前行,当他们走到一个还能离开的出口时,将从该出口离开公园。特别地,当两个人同时走到一个只能允许 11 个人离开的出口时,编号小的那个人能从该出口离开,编号较大的人将继续前进。

现在给定 nn 个人所在的起始位置与他们的前进方向,请你求出每个人从哪个出口离开,若编号为 ii 的 人从 kik_i 号出口离开,你只需要给出 i×kii\times k_i 的异或和,即:

$$(1\times k_1) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n) $$

其中 xor\operatorname{xor} 是位异或运算。特别地若一个人最后无法离开,则他的 ki=0k_i = 0

输入格式

第一行三个正整数 n,m,Ln, m, L,意义见题目描述。

第二行 m1m - 1 个正整数 ai(2im)a_i(2\le i \le m) 表示出口位置。保证 aia_i 严格递增。

第三行 mm 个正整数 lil_i 表示出口的人数限制。

接下来 nn 行每行两个整数 si,bi(1in)s_i,b_i(1 \le i \le n)。若 sis_i00 表示编号为 ii 的人前进方向是逆时针方向,为 11 表示是顺时针方向。 bib_i 表示编号为 ii 的人的起始位置为:离 11 号出口逆时针方向 bib_i 米的位置。

输出格式

仅一行一个整数表示答案。

3 2 5
2
2 1
0 1
1 3
0 4
3
3 2 5
2 
1 1
0 0 
0 2 
0 1
5

提示

【输入输出样例 1 说明】

编号为 1,2,31 ,2, 3 的人分别从 2,1,12, 1, 1 号出口离开。

【输入输出样例 2 说明】

编号为 1,21,2 的人分别从 1,21 ,2 号出口离开,编号为 33 的人无法离开公园。

【数据规模与约定】

对于 12%12\% 的数据:n,m,L10n, m, L \le 10
对于 32%32\% 的数据:n,m100n, m \le 100L1000L \le 1000
对于 52%52\% 的数据:n,m1000n, m \le 1000
另有 20%20\% 的数据:n,m10000n, m \le 10000,所有 si=0s_i = 0
对于 100%100\% 的数据:1n,m2×1051 \le n,m \le 2 \times 10^5 2L1092 \le L \le 10^91ai<L1\le a_i <L1lin1\le l_i \le nsi{0,1}s_i\in\{0,1\}0bi<L0\le b_i<L