← 返回题目列表

AtCoder · joig2024_f

F. 感染模拟

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

配点: 100 点

問題文

EGOI食堂昨天 N 位顾客来过。顾客有 1 它们的编号最大为 N 被编号为,客人 i (1 \leqq i \leqq N的到店时间是 L_i,离店时间是 R_i 。 今天,客人中 1 人被发现以现正在JOI国流行的新型传染病X的感染状态到店。

传染病X的很难被感染是一个整数 它由 x 表示。 具体来说, 关于1 \leqq i \leqq N ,客户 i 是 它可能以 1 一名以上感染者同时出现在自助餐厅的总时间 x 在上述时间,客户 i 成为新的感染者。

现在,JOI国家对传染病采取了严格的措施,因此需要准确掌握感染人数。 但问题是,关于谁感染了传染病的信息 x 也未知。

所以 EGOI Shokudo 的经理 Rie 说: 我们决定找出在Q 场景下最终有多少客户会被感染。 j 番目 (1 \leqq j \leqq Q)场景中,第一个感染者成为客户。 P_j ,传播传染病X的难度为 X_j 。

给定有关访问商店的顾客和场景的信息,编写一个程序,输出每个场景的最终感染人数。 然而,即使有人在离开商店时被感染,也会被计入感染人数中。 此外,我们并不认为曾经感染过传染病X的顾客就不再是感染者。

制約

  • 1 \leqq N \leqq 100\,000.
  • 0 \leqq L_i < R_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 100\,000.
  • 1 \leqq P_j \leqq N (1 \leqq j \leqq Q).
  • 1 \leqq X_j \leqq 10^9 (1 \leqq j \leqq Q).
  • 所有输入值都是整数。

小課題

  1. (2 点) L_i = 0 (1 \leqq i \leqq N),R_i = 10 (1 \leqq i \leqq N),Q \leqq 5.
  2. (3 点) L_i = 0 (1 \leqq i \leqq N),Q \leqq 5.
  3. (6 点) L_i = 0 (1 \leqq i \leqq N).
  4. (10 点) N \leqq 500,Q \leqq 5,R_i \leqq 500 (1 \leqq i \leqq N),X_j \leqq 500 (1 \leqq j \leqq Q).
  5. (11 点) N \leqq 500,Q \leqq 5.
  6. (16 点) Q \leqq 5.
  7. (13 点) P_j = 1 (1 \leqq j \leqq Q),L_1 < L_2 < \cdots < L_N,R_1 < R_2 < \cdots < R_N.
  8. (14 点) P_j = 1 (1 \leqq j \leqq Q).
  9. (15 点) R_i - L_i (1 \leqq i \leqq N的最小值是X_j (1 \leqq j \leqq Q) 大于或等于最大值
  10. (10 点)没有额外的限制。

入力

输入按以下格式给出。

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
Q
P_1 X_1
P_2 X_2
\vdots
P_Q X_Q

出力

Q 行。j 行目 (1 \leqq j \leqq 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 满足约束。