← 返回题目列表

Codeforces · 172/C

C. 巴士

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

大学附近有一个公交车站。课程结束了,n个学生停了下来。第 i 个学生将在时间 ti 出现在公交车站(所有 ti 都是不同的)。

我们假设停靠点位于坐标轴 Ox 上,在点 x = 0 处,并且公交车沿射线 Ox 行驶,即朝坐标轴的正方向行驶,然后返回。第 i 个学生需要到达坐标为 xi (xi > 0) 的点。

公交车按照以下算法移动。最初它位于点 0。学生们不断地来到车站并上车。公共汽车的座位容量等于 m 名乘客。当m个学生上车的那一刻,车就开始向坐标轴正方向移动。当最后(第 n)名学生上车时,它也开始移动。公交车以每 1 单位时间 1 单位距离的速度移动,即在时间 y 内行驶距离 y。

每当公交车经过至少一名学生需要下车的地点时,它就会停下来,让这些学生下车。学生需要 1 + [k / 2] 单位的时间才能下车,其中 k 是此时离开的学生人数。表达式[k / 2]表示向下取整k / 2。当最后一个学生离开巴士时,巴士掉头返回到点x = 0。直到到达该点才停止。在给定的时间点,公交车上再次挤满了学生,一切都重复了。

如果学生在没有公交车的情况下到达车站,他们会排成一队并按照来的顺序上车。任何数量的学生在可以忽略不计的时间内上车,你应该假设这不需要任何时间。任何其他行动也不需要时间。巴士上除了学生外没有其他乘客。

编写一个程序来确定每个学生下车的时间。学生下车的时刻是公交车停在学生的目的地站的时刻(尽管事实上这群学生需要一些时间才能下车)。

输入

第一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 105) — 相应的学生人数和公交车可以运送的乘客人数。接下来的 n 行包含对学生的描述,每行一个。每行包含一对整数 ti, xi (1 ≤ ti ≤ 105, 1 ≤ xi ≤ 104)。这些行按照 ti 严格递增的顺序给出。 xi 的值可以重合。

输出

打印 n 个数字 w1, w2, ..., wn, wi — 第 i 个学生下车的时刻。将数字打印在一行上,并用单个空格分隔。

示例

输入 #1

1 10
3 5

输出 #1

8

输入 #2

2 1
3 5
4 5

输出 #2

8 19

输入 #3

5 4
3 5
4 5
5 5
6 5
7 1

输出 #3

11 11 11 11 20

输入#4

20 4
28 13
31 13
35 6
36 4
52 6
53 4
83 2
84 4
87 1
93 6
108 4
113 6
116 1
125 2
130 2
136 13
162 2
166 4
184 1
192 2

输出#4

51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195

注意

在第一个示例中,公共汽车等待第一个学生 3 个单位的时间,并用另外 5 个单位的时间将他送到目的地。所以学生在时间 3 + 5 = 8 的时刻离开了公共汽车。

在第二个样本中,公共汽车的容量等于 1,这就是为什么它将单独驾驶第一个学生。该学生与第一个样本中的学生相同。因此,公共汽车在时间 8 到达目的地,花费 1 + [1 / 2] = 1 单位时间让他下车,并在另外 5 单位时间内返回到 0。即,公交车在时刻14返回公交车站。此时第二个学生已经来到公交车站。于是他立即上车,又多花了 5 个单位的时间到达目的地。他此时到达那里 14 + 5 = 19。

在第三个样本中,公交车等待第四个学生 6 个单位的时间,然后行驶 5 个单位的时间,然后让乘客下车 1 + [4 / 2] = 3 个单位的时间,然后返回 5 个单位的时间,然后驾驶第五个学生 1 个单位的时间。