← 返回题目列表

AtCoder · abc389_f

I. 额定范围

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

分数: 525 点

问题陈述

高桥计划参加 N AtCoder 竞赛。

在 i第届比赛(1 \leq i \leq N),如果他的评分介于 L_i 和 R_i (含),他的评分增加 1.

你被给予 Q 按以下格式查询:

  • 一个整数 给出了 X 。假设高桥的初始评级是 X,参加全部后确定他的评分 N 比赛。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
  • 1 \leq Q \leq 3 \times 10^5
  • 对于每个查询, 1 \leq X \leq 5 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

在这里, \text{query}_i 是 i-第一个查询,格式为:

X

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

5
1 5
1 3
3 6
2 4
4 7
3
3
2
5

示例输出 1

6
6
8

对于第一个查询,评级更改如下:

  • 在第一场比赛中,评分介于 1 和 5,所以它增加了 1,成为 4.
  • 在第二次比赛中,评分不介于 1 和 3,所以它仍然是 4.
  • 在第三次比赛中,评分介于 3 和 6,所以它增加了 1,成为 5.
  • 在第四次比赛中,评分不介于 2 和 4,所以它仍然是 5.
  • 在第五届比赛中,评分介于 4 和 7,所以它增加了 1,成为 6.

对于第二个查询,第 1、2、3 和 5 次比赛中的评分增加,结束于 6.

对于第 3 个查询,第 1、第 3 和第 5 场比赛的评分增加,结束于 8.


示例输入 2

10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000

示例输出 2

8
2002
2003
2402
500001
2800
1007

示例输入 3

15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580

示例输出 3

287946
296269
224599
101453
336997
390315
323363
177075
11431
8580