← 返回题目列表

AtCoder · pakencamp_2025_day2_c

C. 帕塔罗的作品

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

配点 : 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
  • 所有输入均为整数

小課題

  1. (10 点) X\leq 10
  2. (15 点) P_i\gt 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 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

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 满足约束。