日本情報オリンピック 第4回 女性部門

2024年1月22日
情報オリンピック日本委員会

問題文

EGOI 食堂には昨日 N 人の客が来店した． 客には 1 から N までの番号が付けられており，客 i (1 ≦ i ≦ N) の来店時刻は L_i，退店時刻は R_i であった． そして今日，客のうち 1 人が，現在 JOI 国で流行している新型の感染症 X に感染した状態で来店したことが明らかになった．

感染症 X の感染しづらさは整数 x で表される． 具体的には，1 ≦ i ≦ N について，客 i が 1 人以上の感染者と同時に食堂内にいた時間の累計が x 以上となったタイミングで，客 i は新たに感染者となる．

さて，JOI 国では厳格な感染症対策を行っているため，感染者数を正確に把握しなければならない． しかし困ったことに，誰が感染症 X に感染したかの情報は得られておらず，感染しづらさを表す整数 x も分かっていない．

そこで EGOI 食堂の店長である理恵さんは，Q 個のシナリオについて，最終的に何人の客が感染するのかを求めることにした． j 番目 (1 ≦ j ≦ Q) のシナリオでは，最初の感染者が客 P_j のみであり，感染症 X の感染しづらさが X_j である．

来店した客およびシナリオの情報が与えられたとき，それぞれのシナリオにおける最終的な感染者数を出力するプログラムを作成せよ． ただし，退店時刻ちょうどに感染した場合も，感染者数に含めるものとする． また，感染症 X に一度感染した客が感染者でなくなることは考えないものとする．

制約

• 1 ≦ N ≦ 100 000．
• 0 ≦ L_i ＜ R_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ Q ≦ 100 000．
• 1 ≦ P_j ≦ N (1 ≦ j ≦ Q)．
• 1 ≦ X_j ≦ 10⁹ (1 ≦ j ≦ Q)．
• 入力される値はすべて整数である．

小課題

1. (2 点) L_i = 0 (1 ≦ i ≦ N)，R_i = 10 (1 ≦ i ≦ N)，Q ≦ 5．
2. (3 点) L_i = 0 (1 ≦ i ≦ N)，Q ≦ 5．
3. (6 点) L_i = 0 (1 ≦ i ≦ N)．
4. (10 点) N ≦ 500，Q ≦ 5，R_i ≦ 500 (1 ≦ i ≦ N)，X_j ≦ 500 (1 ≦ j ≦ Q)．
5. (11 点) N ≦ 500，Q ≦ 5．
6. (16 点) Q ≦ 5．
7. (13 点) P_j = 1 (1 ≦ j ≦ Q)，L₁ ＜ L₂ ＜ … ＜ L_N，R₁ ＜ R₂ ＜ … ＜ R_N．
8. (14 点) P_j = 1 (1 ≦ j ≦ Q)．
9. (15 点) R_i - L_i (1 ≦ i ≦ N) の最小値は，X_j (1 ≦ j ≦ Q) の最大値以上である．
10. (10 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
L₁   R₁
L₂   R₂
︙
L_N   R_N
Q
P₁   X₁
P₂   X₂
︙
P_Q   X_Q

出力

Q 行出力せよ．j 行目 (1 ≦ j ≦ Q) には，j 番目のシナリオにおける最終的な感染者数を出力せよ．

入出力例

入力例 1
4
10 40
20 80
45 60
70 95
1
1 15

出力例 1
3

1 番目のシナリオでは，最初の感染者が客 1，感染症 X の感染しづらさが 15 であるため，以下のようにして感染が広がる．

• 時刻 10 に客 1 が来店する．
• 時刻 20 に客 2 が来店する．
• 時刻 35 に客 2 が 1 人以上の感染者と同時に食堂内にいた時間の累計が 15 となり，客 2 が感染する．
• 時刻 40 に客 1 が退店する．
• 時刻 45 に客 3 が来店する．
• 時刻 60 に客 3 が 1 人以上の感染者と同時に食堂内にいた時間の累計が 15 となり，客 3 が感染する．同時に，客 3 が退店する．
• 時刻 70 に客 4 が来店する．
• 時刻 80 に客 2 が退店する．
• 時刻 95 に客 4 が退店する．客 4 が 1 人以上の感染者と同時に食堂内にいたのは時刻 70 から時刻 80 までであり，時間の累計は 10 であるため，客 4 は感染しない．

最終的に客 1, 2, 3 の 3 人が感染するため，1 行目には 3 を出力する．

この入力例は小課題 4, 5, 6, 8, 9, 10 の制約を満たす．

入力例 2
8
0 30
0 90
0 80
0 60
0 20
0 40
0 70
0 50
3
1 30
1 40
4 50

出力例 2
7
1
5

1 番目のシナリオでは，最終的に客 1, 2, 3, 4, 6, 7, 8 の 7 人が感染するため，1 行目には 7 を出力する．

2 番目のシナリオでは，最終的に客 1 の 1 人が感染するため，2 行目には 1 を出力する．

3 番目のシナリオでは，最終的に客 2, 3, 4, 7, 8 の 5 人が感染するため，3 行目には 5 を出力する．

この入力例は小課題 2, 3, 4, 5, 6, 10 の制約を満たす．

入力例 3
5
0 10
0 10
0 10
0 10
0 10
4
1 9
1 10
1 11
1 1000000000

出力例 3
5
5
1
1

この入力例は小課題 1, 2, 3, 5, 6, 8, 10 の制約を満たす．

入力例 4
7
38 61
13 27
10 54
22 56
49 75
27 47
70 99
1
3 10

出力例 4
6

この入力例は小課題 4, 5, 6, 9, 10 の制約を満たす．

入力例 5
10
10 20
11 21
13 23
16 26
20 30
25 35
31 41
38 48
46 56
80 90
4
1 3
1 6
1 8
1 10

出力例 5
8
5
3
1

この入力例は小課題 4, 5, 6, 7, 8, 9, 10 の制約を満たす．

入力例 6
7
10 54
38 61
13 27
22 56
49 75
27 47
70 99
5
1 3
1 6
1 9
1 12
1 15

出力例 6
7
6
6
6
4

この入力例は小課題 4, 5, 6, 8, 10 の制約を満たす．

入力例 7
7
38 61
13 27
10 54
22 56
49 75
27 47
70 99
5
1 10
2 10
3 10
4 10
5 10

出力例 7
4
6
6
5
2

この入力例は小課題 4, 5, 6, 9, 10 の制約を満たす．