配点 : 100 点
問題文
海雀帕塔罗 (Puffin Pataro) 是一位在世界各地展开翅膀的插画家,以诚实回应他的众多请求而闻名。
Pataro 从现在开始将收到请求。输入的请求是 N 件,i 第一个请求是时间 T_i 奖励是 P_i ,所需的完美程度是 Q_i 。奇怪的是,P_i 都是不同的。
帕塔罗是时候了 按 1,2,\dots 的顺序执行以下操作。
- 首先,检查当时传入的请求。最初,这些请求的进度是 0 。
- 如果您有任何未完成的任务,请选择奖励最高的任务并跟踪您的进度。 1 增加。进展 等于 Q_i 的请求结束。
在规划日程时,帕塔罗意识到他的熟人首席运营官 K 可能会突然提出请求。帕塔罗是 我正在考虑 X 场景。 第i 场景如下。
- K运营经理表示,时间 t_i 的奖励 p_i ,所需的完美程度 提交 q_i 请求。奇怪的是, 不包括P 至 该值是 p_i 。
对于每个场景,创建一个程序来查找经理 K 的请求结束的时间。
制約
- 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\ne P_j (i\ne 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 \ne P_j
- 1\leq q_i\leq 10^9
- 所有输入均为整数
小課題
- (10 点) X\leq 10
- (15 点) P_i\gt P_{i+1}
- (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
- (55 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
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 个场景的答案。
入力例 1
5 1 4 4 1 8 2 2 6 5 3 10 1 4 2 1 3 2 9 2 1 15 10 3 1 1
出力例 1
4 10 14
奖励是 p ,所需的完美程度是 请求 q 的请求 表示为 (p,q) 。 在第
1 个场景中,帕塔罗的行为如下。 请求
- 時刻 1 输入 (4,4),(8,2) 。请求有最高奖励 (8,2) 所以,请求 (8,2) 进展 1 增加。
- 時刻 2 输入 (6,5),(9,2) 。请求有最高奖励 (9,2) 所以,请求 (9,2) 进展 1 增加。
- 時刻 3 输入 (10,1) 。请求有最高奖励 (10,1) 所以,请求 (10,1) 进展 1 增加。进展 等于 1 现在,该请求结束。
- 時刻 4 输入 (2,1) 。请求有最高奖励 (9,2) 所以,请求 (9,2) 进展 1 增加。进展 等于 2 现在,该请求结束。
来自 K 操作经理的请求。 (9,2) 是时间 它以 4 结尾,所以4 。
此输入是一个小作业 1,3,4 满足约束。
入力例 2
15 19271058196 967824729 152036485 22712438628 910500852 981520310 140039456534 857077284 620411718 250480340689 769431650 298766521 251317817929 744280520 361324668 274195603603 715892722 480968805 344670306080 499774361 297846843 404902144817 419370025 285187325 520643152574 320064892 924193632 521915710072 249168130 628902494 543856067506 245532751 755031424 561032100177 239276621 713892371 710671228979 198319687 722757772 786820954868 164832983 69837030 946667800961 80707350 486834509 15 759622046068 88860862 423817262 86416230707 596982638 272961036 222135105453 623807668 225447688 987307024314 434140395 210989591 284114340148 853214705 836365490 935147463515 366719378 859904884 22078598728 490910900 362117198 519370635632 736444921 422952344 909241707938 29032918 112179585 687828700252 980166390 487330736 588669383658 735908347 528451855 828303497438 455644532 870392056 969530498200 491489928 888795971 436550659389 138264655 343910843 548244874878 118927479 759025737
出力例 2
760045863329 86689191742 222360553140 987518013904 284950705637 936007368398 22440715925 519793587975 909353887522 688316030987 589197835512 829173889493 970419294170 436894570231 549003900614
此输入是一个小作业 2,4 满足约束。