AT_pakencamp_2025_day2_c Pataro's Work

身为享誉全球的插画师，Puffin 的 Pataro 以认真对待每一个委托而闻名。 现在，Pataro 将会收到 $N$ 个委托，第 $i$ 个委托在时刻 $T_i$ 到来，报酬为 $P_i$，所需完成度为 $Q_i$。奇妙的是，所有的 $P_i$ 均不相同。 Pataro 会按 $1,2,\dots$ 的顺序在每个时刻进行如下操作： - 首先，查看在该时刻到来的所有委托。这些委托的进度初始为 $0$。 - 如果还有未完成的委托，则从中选择报酬最高的一个，令其进度增加 $1$。当进度等于 $Q_i$ 时，这个委托就算完成了。 在制定日程的时候，Pataro 意识到，熟人 K 主管有可能会突然插入新的委托。于是 Pataro 考虑了 $X$ 种情景。第 $i$ 个情景如下： - K 主管会在时刻 $t_i$ 插入一份报酬为 $p_i$、所需完成度为 $q_i$ 的委托。神奇的是，$p_i$ 不在 $P$ 中。 请你为每个情景编写程序，输出 K 主管的委托完成的时刻。

输入按照如下格式由标准输入读取。 > $N$ $T_1$ $P_1$ $Q_1$ $T_2$ $P_2$ $Q_2$ $\vdots$ $T_N$ $P_N$ $Q_N$ $X$ $t_1$ $p_1$ $q_1$ $t_2$ $p_2$ $q_2$ $\vdots$ $t_X$ $p_X$ $q_X$

输出共 $X$ 行。 第 $i$ 行输出第 $i$ 个情景下 K 主管委托完成的时刻。

## 小子任务 1.（10 分）$X \leq 10$ 2.（15 分）$P_i > P_{i+1}$ 3.（20 分）$T_i, t_i \leq 2\times 10^5, \sum_{i=1}^N Q_i \leq 2\times 10^5, q_i \leq 2\times 10^5$ 4.（55 分）没有额外限制。 ## 样例解释 1 用 $(p,q)$ 表示报酬为 $p$、要求完成度为 $q$ 的委托。 对于第 $1$ 个情景，Pataro 的操作如下： - 时刻 $1$，委托 $(4,4), (8,2)$ 到达。报酬最高的是 $(8,2)$，其进度加 $1$。 - 时刻 $2$，委托 $(6,5), (9,2)$ 到达。报酬最高的是 $(9,2)$，进度加 $1$。 - 时刻 $3$，委托 $(10,1)$ 到达。报酬最高的是 $(10,1)$，进度加 $1$，完成。 - 时刻 $4$，委托 $(2,1)$ 到达。报酬最高的是 $(9,2)$，进度加 $1$，进度达到 $2$，完成。 K 主管的委托 $(9,2)$ 在时刻 $4$ 完成，因此输出 $4$。 本输入符合小子任务 $1,3,4$ 的限制。 ## 样例解释 2 本输入符合小子任务 $2,4$ 的限制。 # 数据范围与约定 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq T_1 \leq T_2 \leq \dots \leq T_N \leq 10^{14}$ - $1 \leq P_i \leq 10^9$ - $P_i \neq P_j \ (i \neq j)$ - $1 \leq Q_i \leq 10^9$ - $1 \leq X \leq 2 \times 10^5$ - $1 \leq t_i \leq 10^{14}$ - $1 \leq p_i \leq 10^9$ - $p_i \neq P_j$ - $1 \leq q_i \leq 10^9$ - 所有输入均为整数。 由 ChatGPT 5 翻译