ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4822: Processing Queries 处理查询

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：3 通过：3
提交提交记录统计Web Board

题目描述

在这个问题中，你必须模拟单线程服务器的工作流程。有n要处理的查询，tn将在此时收到i-th并且需要处理dn时间单位。都tn保证是不同的。

当查询出现时，服务器可能会以三种可能的方式做出反应：

  1. 如果服务器空闲且查询队列为空，则服务器将立即开始处理此查询。
  2. 如果服务器繁忙且少于b队列中的查询，然后将新查询添加到队列末尾。
  3. 如果服务器繁忙并且已经有b查询在队列中挂起，则新查询将被拒绝，永远不会被处理。

一旦服务器完成处理某些查询，它就会从队列中选择一个新查询（当然，如果它不为空）。如果在某个时刻出现新查询x，并且服务器在同一时刻完成处理另一个查询，我们认为第一个查询是从队列中选取的，然后才出现新查询。

对于每个查询，查找服务器完成处理它的时刻，如果此查询将被拒绝，则打印 -1。

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 ti and needs to be processed for di units of time. All ti 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.
Input
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 ti and di (1≤ti,di≤109), where ti is the moment of time when the i-th query appears and di is the time server needs to process it. It is guaranteed that ti-1<ti for all i>1.
Output
打印 n 个整数的序列 e 1，e 2,...,e n，其中 e i 是服务器完成处理第 i 个查询的时刻（查询按它们在输入中出现的顺序编号）或 -1（如果相应的查询将被拒绝）。
Examples
Input 
5 1
2 9
4 8
10 9
15 2
19 1
Output 
11 19 -1 21 22
Input 
4 1
2 8
4 8
10 9
15 2
Output 
10 18 27 -1
Note
考虑第一个示例。
  1. 服务器将在第 2 刻开始处理第一个查询，并在第 11 刻完成处理它。
  2. 此时出现 4 秒查询并进入队列。
  3. 此时出现 10 第三个查询。但是，服务器仍在忙于查询 1，b=1，并且队列中已经有查询 2 挂起，因此第三个查询刚刚被拒绝。
  4. 此时服务器11将完成处理第一个查询，并将从队列中获取第二个查询。
  5. 此时出现 15 第四个查询。当服务器当前繁忙时，它会进入队列。
  6. 此时 19 同时发生两个事件：服务器完成以继续第二个查询，第五个查询出现。如上面的语句中所述，第一个服务器将完成处理第二个查询，然后它将从队列中选择第四个查询，然后才会出现第五个查询。当队列为空时，第五个查询继续。
  7. 服务器在当前 4 完成处理第 21 号查询。从队列中选取第 5 个查询。
  8. 服务器在当前 5 完成处理第 22 号查询。

输入格式

输入的第一行包含两个整数n和b (1≤n,b≤200000) — 查询数和查询队列的最大可能大小。

然后跟随n带有查询说明的行（按时间顺序）。每个描述由两个整数组成 ti 和di (1≤ti,di≤109)，其中 ti 是i-th 查询出现并di 是服务器需要处理它的时间。保证 ti-1<ti 对于所有i>1成立 。

输出格式

打印 n 个整数的序列 e 1，e 2,...,e n，其中 e i 是服务器完成处理第 i 个查询的时刻（查询按它们在输入中出现的顺序编号）或 -1（如果相应的查询将被拒绝）。

输入样例 复制 

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

输出样例 复制 

11 19 -1 21 22

数据范围与提示

考虑第一个示例。
  1. 服务器将在第 2 刻开始处理第一个查询，并在第 11 刻完成处理它。
  2. 此时出现 4 秒查询并进入队列。
  3. 此时出现 10 第三个查询。但是，服务器仍在忙于查询 1，b=1，并且队列中已经有查询 2 挂起，因此第三个查询刚刚被拒绝。
  4. 此时服务器11将完成处理第一个查询，并将从队列中获取第二个查询。
  5. 此时出现 15 第四个查询。当服务器当前繁忙时，它会进入队列。
  6. 此时 19 同时发生两个事件：服务器完成以继续第二个查询，第五个查询出现。如上面的语句中所述，第一个服务器将完成处理第二个查询，然后它将从队列中选择第四个查询，然后才会出现第五个查询。当队列为空时，第五个查询继续。
  7. 服务器在当前 4 完成处理第 21 号查询。从队列中选取第 5 个查询。
  8. 服务器在当前 5 完成处理第 22 号查询。

分类标签