← 返回题目列表

AtCoder · abc423_d

G. 漫长的等待

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

分数: 400 点

问题陈述

有餐厅最多可容纳 K 客户同步。这家餐厅前面有一条小街,那里有一个队列。

时间 0,餐厅里没有顾客,队列也空无一人。

今天, N 预定有一批顾客来,编号从 1 to N 按照到达的顺序。集团 i 包括 C_i 人,在时间加入队列末尾 A_i,然后离开餐厅 B_i 输入后的时间单位。

同时满足以下两个条件时,各组最早离开队列进入餐厅:

  • 该组位于队列的前面。换句话说,该组是当时仍在队列中最早加入的组。
  • 当该团体中的人数与当前在餐厅中的所有团体的人数(包括在该时间进入并排除离开的人数)相加时,有 K 人或更少。

找出各组进入餐厅的时间​​。

约束

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq K \leq 10^7
  • 1 \leq A_i, B_i \leq 10^7 (1 \leq i \leq N)
  • A_1 < \dots < A_N
  • 1 \leq C_i \leq K (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 B_1 C_1
\vdots
A_N B_N C_N

输出

输出 N 行。的 i- 第行 (1 \leq i \leq N) 应包含组的时间 i 以整数形式输入餐厅。


示例输入 1

4 10
30 300 3
60 45 4
90 45 5
120 45 2

示例输出 1

30
60
105
120

各组的进出流程如下:

  • 时间 30,组 1 加入队列并立即进入,使得餐厅的顾客数量 3.
  • 时间 60,组 2 加入队列并立即进入,使得餐厅的顾客数量 7.
  • 时间 90,组 3 加入队列。
  • 时间 105,组 2 离开,使得餐厅的顾客数量 3。紧接着,组 3 输入,使得餐厅的顾客数量 8.
  • 时间 120,组 4 加入队列并立即进入,使得餐厅的顾客数量 10.
  • 时间 150,组 3 离开,使得餐厅的顾客数量 5.
  • 时间 165,组 4 离开,使得餐厅的顾客数量 3.
  • 时间 330,组 1 离开,使得餐厅的顾客数量 0.

示例输入 2

4 10
30 300 10
60 45 2
90 45 3
120 45 4

示例输出 2

30
330
330
330

各组的进出流程如下:

  • 时间 30,组 1 加入队列并立即进入,使得餐厅的顾客数量 10.
  • 时间 60,组 2 加入队列。
  • 时间 90,组 3 加入队列。
  • 时间 120,组 4 加入队列。
  • 时间 330,组 1 离开,使得餐厅的顾客数量 0。紧接着,各组 输入 2,3,4 ,计算餐厅内的顾客数量 9.
  • 时间 375,组 2,3,4 离开,使得餐厅内的顾客数量 0.

示例输入 3

10 24
279290 9485601 1
1094410 8022270 4
1314176 7214745 5
1897674 5924694 10
1921802 5769841 4
2506394 2765234 2
2558629 2727489 9
2681289 4061363 5
3022540 2291905 3
4407692 1313036 8

示例输出 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857