AT_joig2024_f 感染シミュレーション (Infection Simulation)

EGOI 食堂昨天迎来了 $N$ 名顾客。每位顾客都被分配了 $1$ 到 $N$ 的编号，其中第 $i$ 位顾客（$1 \leq i \leq N$）的进店时间为 $L_i$，离店时间为 $R_i$。如今已知，其中有一位顾客在到店时已感染了目前在 JOI 国流行的新型传染病 X。 传染病 X 的**传染难度**以整数 $x$ 表示。具体而言，对每位顾客 $i$（$1 \leq i \leq N$），如果其与至少一名感染者同时在食堂内的累计时间达到 $x$，那么他就会成为新的感染者。 由于 JOI 国采取了严格的防疫政策，必须精确掌握感染者人数。但令人头疼的是，具体是哪位顾客在进店时感染了感染症 X 不明，传染难度 $x$ 也不清楚。 因此，EGOI 食堂的店长理惠决定针对 $Q$ 个场景，分别计算最终有多少人被感染。第 $j$ 个场景（$1 \leq j \leq Q$）里，编号为 $P_j$ 的顾客是唯一最初的感染者，且传染病 X 的传染难度为 $X_j$。 给定顾客和各个场景的信息，请编写程序，输出每个场景下最终被感染顾客的人数。注意，如果某人正好在离店时刻感染，也计入感染人数。同时，已感染的顾客不会变回未感染者。

输入格式如下： > $N$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $…$ > $L_N$ $R_N$ > $Q$ > $P_1$ $X_1$ > $P_2$ $X_2$ > $…$ > $P_Q$ $X_Q$

输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 个场景下最终被感染顾客的人数。

## 子任务 1. （2 分）$L_i = 0$（$1 \leq i \leq N$），$R_i = 10$（$1 \leq i \leq N$），$Q \leq 5$。 2. （3 分）$L_i = 0$（$1 \leq i \leq N$），$Q \leq 5$。 3. （6 分）$L_i = 0$（$1 \leq i \leq N$）。 4. （10 分）$N \leq 500$，$Q \leq 5$，$R_i \leq 500$（$1 \leq i \leq N$），$X_j \leq 500$（$1 \leq j \leq Q$）。 5. （11 分）$N \leq 500$，$Q \leq 5$。 6. （16 分）$Q \leq 5$。 7. （13 分）$P_j = 1$（$1 \leq j \leq Q$），$L_1 < L_2 < … < L_N$，$R_1 < R_2 < … < R_N$。 8. （14 分）$P_j = 1$（$1 \leq j \leq Q$）。 9. （15 分）$\min_{1 \leq i \leq N}(R_i - L_i)$ 不小于 $\max_{1 \leq j \leq Q}(X_j)$。 10. （10 分）无额外限制。 ## 样例说明 1 在第 $1$ 个场景中，最初的感染者是顾客 $1$，传染病 X 的传染难度为 $15$，感染传播过程如下： - 时刻 $10$，顾客 $1$ 进店。 - 时刻 $20$，顾客 $2$ 进店。 - 时刻 $35$，顾客 $2$ 与至少一名感染者在食堂共处的累计时间达到 $15$，顾客 $2$ 被感染。 - 时刻 $40$，顾客 $1$ 离店。 - 时刻 $45$，顾客 $3$ 进店。 - 时刻 $60$，顾客 $3$ 与至少一名感染者在食堂共处的累计时间达到 $15$，顾客 $3$ 被感染，与此同时顾客 $3$ 离店。 - 时刻 $70$，顾客 $4$ 进店。 - 时刻 $80$，顾客 $2$ 离店。 - 时刻 $95$，顾客 $4$ 离店。顾客 $4$ 与至少一名感染者共处总计 $10$ 单位时间，未达到传染难度 $15$，未被感染。 最终，顾客 $1, 2, 3$ 共 $3$ 人被感染，因此第 $1$ 行输出 $3$。 此输入满足子任务 $4, 5, 6, 8, 9, 10$ 的限制。 ## 样例说明 2 在第 $1$ 个场景下，最终顾客 $1, 2, 3, 4, 6, 7, 8$ 共 $7$ 人感染，因此第 $1$ 行输出 $7$。 在第 $2$ 个场景中，最终仅有顾客 $1$ 感染，因此第 $2$ 行输出 $1$。 在第 $3$ 个场景中，最终顾客 $2, 3, 4, 7, 8$ 共 $5$ 人感染，因此第 $3$ 行输出 $5$。 此输入满足子任务 $2, 3, 4, 5, 6, 10$ 的限制。 ## 样例说明 3 此输入满足子任务 $1, 2, 3, 5, 6, 8, 10$ 的限制。 ## 样例说明 4 此输入满足子任务 $4, 5, 6, 9, 10$ 的限制。 ## 样例说明 5 此输入满足子任务 $4, 5, 6, 7, 8, 9, 10$ 的限制。 ## 样例说明 6 此输入满足子任务 $4, 5, 6, 8, 10$ 的限制。 ## 样例说明 7 此输入满足子任务 $4, 5, 6, 9, 10$ 的限制。 ## 数据范围 - $1 \leq N \leq 100\,000$。 - $0 \leq L_i < R_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq Q \leq 100\,000$。 - $1 \leq P_j \leq N$（$1 \leq j \leq Q$）。 - $1 \leq X_j \leq 10^9$（$1 \leq j \leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译