← 返回题目列表

AtCoder · jsc2025_final_e

E. 礼貌很重要

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

AtCoder 和 BatCoder 将展开一场企业大战。 AtCoder 有 编号至 1 它们的编号最大为 N 编号最多为 N 员工 i 的强度是 A_i,礼貌是 P_i 。 蝙蝠编码器也 1 它们的编号最大为 N 编号最多为 N 员工 i 的强度是 B_i 。

企业竞争是按以下步骤进行的事件。

  • 首先,AtCoder 0 以上 N 的整数 声明 k 。
  • 此后,两家公司都从实力较强的一家开始。 k 选择员工进行相互竞争(决胜局是可选的)。
  • 本次企业竞赛得分为(AtCoder 参赛成员的实力总和)-(BatCoder 参赛成员的实力总和) 变为。

顺便说一句,AtCoder 正计划 我们安排了 Q 工作面试。 i 实力 X_i,礼貌 Y_i 候选人将会出现。 在这次面试之前,AtCoder 员工最起码的礼貌是什么? 比方说 z 。 如果 Y_i < z 如果是,则结束面试而不雇用该候选人。 如果 z < Y_i 然后雇用该候选人并 z 员工将被解雇。 请注意,在此问题中,仅给出所有字符都具有不同礼貌值的输入。 关于

各 t=0,1,\ldots,Q ,只是 t 第一轮面试结束后将进行公司间的竞争。 每个 求 t 企业竞赛的最高可能得分。

在这个问题中,X_i,Y_i 的值为 除非您在 t=i-1 中询问答案,否则您不会知道。 请检查输入部分以获取更多详细信息。 所有

制約

  • 1 \leq N \leq 250000
  • 1 \leq Q \leq 250000
  • 0 \leq A_i,B_i,P_i,X_i,Y_i < 2^{30}
  • P_1,\ldots,P_N,Y_1,\ldots,Y_Q 值都不同
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N Q
A_1 P_1
A_2 P_2
\vdots
A_N P_N
B_1 B_2 \ldots B_N
X_1' Y_1'
X_2' Y_2'
\vdots
X_Q' Y_Q'

在这里, 是X_i',Y_i' 是 X_i,Y_i 的加密值, 答案在0 \leq X_i',Y_i' < 2^{30} 很满意。 当 t=i-1 答案在 ans_{i-1} 然后,X_i,Y_i 的值可以如下恢复。

  • X_i = X_i' \oplus (ans_{i-1} \pmod{2^{30}})
  • Y_i = Y_i' \oplus (ans_{i-1} \pmod{2^{30}})

在这里, 是\oplus 以位为单位 \mathrm{XOR} 代表一个操作。 当

出力

Q+1 行。 i 行中,t=i-1 时打印答案。


入力例 1

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

出力例 1

2
1
  • t=0:AtCoder 最好声明 k=3 。 AtCoder参赛成员的总实力为 4+3+1=8BatCoder参赛成员的总实力为 3+3+0=6 得分为 它变成 8-6=2 。
  • 1 第二次采访: (X_i,Y_i)=(1,3) 。 AtCoder 是一种优势 3,礼貌 0 解雇员工并加强 雇用 1,礼貌 3 员工。
  • t=1:AtCoder 最好声明 k=1 。 AtCoder参赛成员的总实力为 4BatCoder参赛成员的总实力为 3 得分为 它变成 4-3=1 。

入力例 2

6 5
12 4
11 15
0 6
4 0
8 5
4 8
2 8 8 13 7 6
9 1
5 8
0 9
15 12
4 2

出力例 2

2
6
2
0
5
5

入力例 3

10 13
92788721 542214255
293089679 516436321
669808382 626939225
238515753 666162008
242072611 97945595
466154699 275263259
1060112845 48898052
226548347 163247932
916132312 319810611
305065449 33194413
675278910 810708817 766536096 776055247 74986938 522734573 95413623 815637961 455070319 641005226
559678870 63240180
190319444 640573455
820546404 426868109
801203381 602683328
1028200997 844428795
592163827 328798860
890167861 914517637
1020849514 15202582
759333575 276170982
277756469 655405268
172240995 894346766
1012534420 985317173
392457922 844853509

出力例 3

349898379
471883737
187826139
415877835
572657577
572657577
572657577
335086730
209706130
195009665
195009665
107677877
273259909
273259909