分数: 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