/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
高橋君はAtCoderのコンテストに N 回参加しようとしています。
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 個目のクエリでは以下のようにコンテストごとにレーティングが変化します。
- 1 回目のコンテストではレーティングが 1 以上 5 以下のため、レーティングが 1 増加し 4 になります。
- 2 回目のコンテストではレーティングが 1 以上 3 以下でないため、レーティングが増加せず 4 のままです。
- 3 回目のコンテストではレーティングが 3 以上 6 以下のため、レーティングが 1 増加し 5 になります。
- 4 回目のコンテストではレーティングが 2 以上 4 以下でないため、レーティングが増加せず 5 のままです。
- 5 回目のコンテストではレーティングが 4 以上 7 以下のため、レーティングが 1 増加し 6 になります。
2 個目のクエリでは 1,2,3,5 回目のコンテストでレーティングが 1 増加するため、レーティングは 6 になります。
3 個目のクエリでは 1,3,5 回目のコンテストでレーティングが 1 増加するため、レーティングは 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
Score : 525 points
Problem Statement
Takahashi plans to participate in N AtCoder contests.
In the i-th contest (1 \leq i \leq N), if his rating is between L_i and R_i (inclusive), his rating increases by 1.
You are given Q queries in the following format:
- An integer X is given. Assuming that Takahashi's initial rating is X, determine his rating after participating in all N contests.
Constraints
- 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
- For each query, 1 \leq X \leq 5 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Here, \text{query}_i is the i-th query in the form:
X
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
5 1 5 1 3 3 6 2 4 4 7 3 3 2 5
Sample Output 1
6 6 8
For the 1st query, the rating changes as follows:
- In the 1st contest, the rating is between 1 and 5, so it increases by 1, becoming 4.
- In the 2nd contest, the rating is not between 1 and 3, so it remains 4.
- In the 3rd contest, the rating is between 3 and 6, so it increases by 1, becoming 5.
- In the 4th contest, the rating is not between 2 and 4, so it remains 5.
- In the 5th contest, the rating is between 4 and 7, so it increases by 1, becoming 6.
For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at 6.
For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at 8.
Sample Input 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
Sample Output 2
8 2002 2003 2402 500001 2800 1007
Sample Input 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
Sample Output 3
287946 296269 224599 101453 336997 390315 323363 177075 11431 8580