配点: 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).
- 所有输入值都是整数。
小課題
- (2 点) L_i = 0 (1 \leqq i \leqq N),R_i = 10 (1 \leqq i \leqq N),Q \leqq 5.
- (3 点) L_i = 0 (1 \leqq i \leqq N),Q \leqq 5.
- (6 点) L_i = 0 (1 \leqq i \leqq N).
- (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).
- (11 点) N \leqq 500,Q \leqq 5.
- (16 点) Q \leqq 5.
- (13 点) P_j = 1 (1 \leqq j \leqq Q),L_1 < L_2 < \cdots < L_N,R_1 < R_2 < \cdots < R_N.
- (14 点) P_j = 1 (1 \leqq j \leqq Q).
- (15 点) R_i - L_i (1 \leqq i \leqq N的最小值是X_j (1 \leqq j \leqq Q) 大于或等于最大值
- (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 满足约束。