CF253E Printer

让我们来考虑一个网络打印机，它的工作方式如下：打印机从时间 0 开始工作。每秒可以打印一页文本。在某些时刻，打印机会收到打印任务。已知打印机总共收到了 $n$ 个任务。我们用 1 到 $n$ 的连续整数为这些任务编号。那么第 $i$ 个任务由三个整数描述：$t_{i}$ 表示任务到达的时间，$s_{i}$ 表示该任务的页数（页面数），$p_{i}$ 表示该任务的优先级。所有任务的优先级均互不相同。 当打印机收到任务后，该任务进入队列，并一直留在队列中，直到该任务的所有页面被打印完成。每当打印机停止打印某页时，或者当它空闲并收到新任务时，打印机会选择要打印的任务。在此时队列中的所有任务中，打印机会选择优先级最高的任务，在接下来的 1 秒内打印该任务尚未打印的页面中的一页。你可以认为任务是在到达时立即进入队列的，因此如果某个任务刚好在时间 $t$ 到达，打印机可以立刻选择它进行打印。 你已经知道了除了其中一个任务以外的所有任务的详细信息：你不知道这个任务的优先级。不过，我们知道这个任务的最后一页被打印完成的时刻。给定这些信息，请你求出该任务的优先级，并确定每个任务最后一页被打印完成的时刻。

第一行包含整数 $n$ （$1 \leq n \leq 50000$）。接下来的 $n$ 行描述各个任务。第 $i$ 行包含三个整数 $t_{i}$、$s_{i}$ 和 $p_{i}$，它们之间用一个空格隔开（$0 \leq t_{i} \leq 10^{9},\ 1 \leq s_{i},p_{i} \leq 10^{9}$）。恰好有一个任务（我们假设它的编号为 $x$）的优先级位置用 $-1$ 替代。所有优先级互不相同。最后一行包含整数 $T$——为编号为 $x$ 的任务的最后一页被打印结束的时刻（$1 \leq T \leq 10^{15}$）。$t_{i}$ 不一定互不相同。输入中的任务顺序是任意的。

第一行输出整数 $p_{x}$——编号为 $x$ 的任务的优先级（$1 \leq p_{x} \leq 10^{9}$，且所有优先级应互不相同）。然后输出 $n$ 个整数，第 $i$ 个数表示编号为 $i$ 的任务最后一页被打印完成的时刻。 保证至少存在一个可行解。如果有多个解，请输出任意一个。

我们来看第一个测试样例。假设未知优先级为 4，则打印机每一秒的处理如下： - 第 1 秒开始（时间 0），队列只有任务 2。打印机打印任务 2 的第一页； - 第 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 秒结束时被打印完成。 由 ChatGPT 5 翻译