Processing Queries

题意翻译

##### 问题描述 有一条单线程的生产线，即同时只能处理一项工作，有 $n$ 个工作申请，第 $i$ 个工作的开始时间为 $t_i$，完成需要 $d_i$ 个单位时间，所有的 $t_i$ 都不相同。 当一项工作申请出现时，生产线会有如下三种处理方案： 1. 如果生产线是空闲的，而且等待队列是空的，则当前申请的工作会被马上执行。 2. 如果生产线正在工作，而且等待队列中的工作少于 $b$ 个，则当前申请的工作会被加入到等待队列的队尾。 3. 如果生产线正在工作，而且等待队列中的工作已经有 $b$ 个，则当前申请的工作会被拒绝，而且再也不会接受该工作的申请。 ##### 输入输出格式 ###### 输入格式 第一行，两个整数 $n$ 和 $b$。 接下来 $n$ 行，每行两个整数 $t_i$ 和 $d_i$。 ###### 输出格式 输出共一行，包含 $n$ 个整数，依次表示 $n$ 个工作的完成时间，如果当前工作被拒绝则输出 $-1$。 ##### 说明/提示 $1 \leq n,b \leq 2\times 10^5$。 $1\leq t_i,d_i \leq 10^9$。 $t_{i-1}<t_i$。

题目描述

In this problem you have to simulate the workflow of one-thread server. There are $ n $ queries to process, the $ i $ -th will be received at moment $ t_{i} $ and needs to be processed for $ d_{i} $ units of time. All $ t_{i} $ are guaranteed to be distinct. When a query appears server may react in three possible ways: 1. If server is free and query queue is empty, then server immediately starts to process this query. 2. If server is busy and there are less than $ b $ queries in the queue, then new query is added to the end of the queue. 3. If server is busy and there are already $ b $ queries pending in the queue, then new query is just rejected and will never be processed. As soon as server finished to process some query, it picks new one from the queue (if it's not empty, of course). If a new query comes at some moment $ x $ , and the server finishes to process another query at exactly the same moment, we consider that first query is picked from the queue and only then new query appears. For each query find the moment when the server will finish to process it or print -1 if this query will be rejected.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ b $ ( $ 1<=n,b<=200000 $ ) — the number of queries and the maximum possible size of the query queue. Then follow $ n $ lines with queries descriptions (in chronological order). Each description consists of two integers $ t_{i} $ and $ d_{i} $ ( $ 1<=t_{i},d_{i}<=10^{9} $ ), where $ t_{i} $ is the moment of time when the $ i $ -th query appears and $ d_{i} $ is the time server needs to process it. It is guaranteed that $ t_{i-1}&lt;t_{i} $ for all $ i&gt;1 $ .

输出格式

Print the sequence of $ n $ integers $ e_{1},e_{2},...,e_{n} $ , where $ e_{i} $ is the moment the server will finish to process the $ i $ -th query (queries are numbered in the order they appear in the input) or $ -1 $ if the corresponding query will be rejected.

输入输出样例

输入样例 #1

5 1
2 9
4 8
10 9
15 2
19 1

输出样例 #1

11 19 -1 21 22 

输入样例 #2

4 1
2 8
4 8
10 9
15 2

输出样例 #2

10 18 27 -1 

说明

Consider the first sample. 1. The server will start to process first query at the moment $ 2 $ and will finish to process it at the moment $ 11 $ . 2. At the moment $ 4 $ second query appears and proceeds to the queue. 3. At the moment $ 10 $ third query appears. However, the server is still busy with query $ 1 $ , $ b=1 $ and there is already query $ 2 $ pending in the queue, so third query is just rejected. 4. At the moment $ 11 $ server will finish to process first query and will take the second query from the queue. 5. At the moment $ 15 $ fourth query appears. As the server is currently busy it proceeds to the queue. 6. At the moment $ 19 $ two events occur simultaneously: server finishes to proceed the second query and the fifth query appears. As was said in the statement above, first server will finish to process the second query, then it will pick the fourth query from the queue and only then will the fifth query appear. As the queue is empty fifth query is proceed there. 7. Server finishes to process query number $ 4 $ at the moment $ 21 $ . Query number $ 5 $ is picked from the queue. 8. Server finishes to process query number $ 5 $ at the moment $ 22 $ .

题意翻译

##### 问题描述 有一条单线程的生产线，即同时只能处理一项工作，有 $n$ 个工作申请，第 $i$ 个工作的开始时间为 $t_i$，完成需要 $d_i$ 个单位时间，所有的 $t_i$ 都不相同。 当一项工作申请出现时，生产线会有如下三种处理方案： 1. 如果生产线是空闲的，而且等待队列是空的，则当前申请的工作会被马上执行。 2. 如果生产线正在工作，而且等待队列中的工作少于 $b$ 个，则当前申请的工作会被加入到等待队列的队尾。 3. 如果生产线正在工作，而且等待队列中的工作已经有 $b$ 个，则当前申请的工作会被拒绝，而且再也不会接受该工作的申请。 ##### 输入输出格式 ###### 输入格式 第一行，两个整数 $n$ 和 $b$。 接下来 $n$ 行，每行两个整数 $t_i$ 和 $d_i$。 ###### 输出格式 输出共一行，包含 $n$ 个整数，依次表示 $n$ 个工作的完成时间，如果当前工作被拒绝则输出 $-1$。 ##### 说明/提示 $1 \leq n,b \leq 2\times 10^5$。 $1\leq t_i,d_i \leq 10^9$。 $t_{i-1}<t_i$。