← 返回题目列表

Codeforces · 253/E

E. 打印机

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

让我们考虑一个具有类似功能的网络打印机。它在时间 0 开始工作。每秒它可以打印一页文本。有时打印机会收到打印任务。我们知道一台打印机接收了n个任务。让我们用从 1 到 n 的连续整数对任务进行编号。那么任务号i由三个整数来表征:ti是任务到来的时间,si是任务的体积(以页为单位),pi是任务的优先级。所有任务的优先级都是不同的。

当打印机接收到任务时,该任务将进入队列并保留在那里,直到打印该任务的所有页面。当打印机停止打印某些页面或空闲并接收新任务时,打印机每次都会选择要打印的页面。在此时队列中的所有任务中,打印机选择优先级最高的任务,下一秒打印该任务中未打印的页面。您可以假设任务立即进入队列,这就是为什么如果任务在时间 t 刚刚到达,打印机就已经可以选择它进行打印。

您将获得有关所有任务的完整信息,但以下任务除外:您不知道该任务的优先级。但是,我们知道该任务的最后一页打印完成的时间。根据此信息,找到未知的优先级值并确定打印机完成打印每个任务的时间点。

输入

第一行包含整数 n (1 ≤ n ≤ 50000)。接下来的 n 行描述了任务。这些行的第 i 行包含三个整数 ti、si 和 pi,用单个空格分隔(0 ≤ ti ≤ 109、1 ≤ si、pi ≤ 109)。恰好有一个任务(假设他的编号是 x)的编号为 -1,而不是优先级。所有的优先事项都是不同的。最后一行包含整数 T — 打印机完成打印任务 x 最后一页的时间 (1 ≤ T ≤ 1015)。数字 ti 不一定不同。输入中的任务以任意顺序写入。

输出

在第一行打印整数 px — 任务编号 x 的优先级(1 ≤ px ≤ 109,记住所有优先级应该不同)。然后打印n个整数,其中第i个表示第i个任务的最后一页打印完成的时刻。

保证至少存在一个解。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
4 3 -1
0 2 2
1 3 3
7

输出 #1

4
7 8 4

输入 #2

3
3 1 2
2 3 3
3 1 -1
4

输出 #2

4
7 6 4

注意

让我们考虑第一个测试用例。假设未知优先级等于 4,则打印机每秒的操作如下:

- 第一秒的开始(时间 0)。队列中有任务2。打印机打印该任务的第一页;
- 第二秒的开始(时间 1)。队列中有任务 2 和 3。打印机打印任务 3 的第一页;
- 第 3 秒(时间 2)的开始。队列中有任务 2 和 3。打印机打印任务 3 的第二页;
- 第 4 秒(时间 3)的开始。队列有任务 2 和 3。打印机打印任务 3 的第三(最后)页。因此,到第 4 秒结束时,该任务将被打印;
- 第 5 秒开始(时间 4)。队列中有任务 2 和 1。打印机打印任务 1 的第一页;
- 第 6 秒开始(时间 5)。队列中有任务 2 和 1。打印机打印任务 1 的第二页;
- 第 7 秒开始(时间 6)。队列有任务 2 和 1。打印机打印任务 1 的第三(最后)页。因此,到第 7 秒结束时,该任务将被打印;
- 第 8 秒开始(时间 7)。队列中有任务 2。打印机打印任务 2 的第二(最后)页。因此,到第 8 秒结束时,该任务将被打印。

最后,按照要求,第 1 号任务将在第 7 秒结束时打印出来。任务2和任务3分别在第8秒和第4秒结束时打印。