← 返回题目列表

Codeforces · 257/E

E. 贪婪电梯

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

国际公司CodeForces的m层(m > 1)办公室建立了先进的电梯控制系统。其工作原理如下。

所有办公楼层均以1到m的整数顺序编号。 t = 0 时刻,电梯在一楼,电梯是空的,其他楼层无人等电梯。接下来,有时 ti (ti > 0) 个人来到电梯。为简单起见,我们假设一个人在报告的时间间隔内仅使用电梯一次。对于每个人,我们都知道三个参数:这个人到达电梯的时间、这个人最初所在的楼层以及他想去的楼层。

电梯在楼层之间的移动如下。在时间 t(t ≥ 0,t 为整数)时,电梯始终处于某个楼层。首先,电梯释放电梯内所有想要到达当前楼层的人员。然后它让所有在这一层等待电梯的人进来。如果一个人恰好在时间 t 到达电梯,那么他有足够的时间进入电梯。我们可以假设所有这些动作(进出电梯)都是立即完成的。之后,电梯决定向哪个方向移动,并在时间 (t + 1) 时电梯到达所选楼层。

电梯通过以下算法选择移动方向。

- 如果电梯是空的,并且当前任何楼层都没有人在等待电梯,则电梯保持在当前楼层。
- 否则,假设电梯位于 x 层(1 ≤ x ≤ m)。然后,elevator 计算方向的“优先级”pup 和 pdown:pup 是大于 x 的楼层等待电梯的人数与电梯内想要到达大于 x 的楼层的人数之和; pdown 是小于 x 的楼层等待电梯的人数与电梯内想要到达小于 x 的楼层的人数之和。如果pup ≥ pdown,则电梯往当前楼层上方一层(即从x层到x + 1层),否则电梯往当前楼层下方一层(即从x层到x - 1层)。

你的任务是模拟电梯的工作,并让每个人告诉电梯到达该人需要的楼层的时间。请注意,电梯足够大,可以同时容纳所有的人。

输入

第一行包含两个以空格分隔的整数:n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 105) — 相应地,建筑物中的人数和楼层数。

接下来的 n 行每行包含三个空格分隔的整数:ti, si, fi (1 ≤ ti ≤ 109, 1 ≤ si, fi ≤ m, si ≠ fi) - 第 i 个人开始等电梯的时间、第 i 个人最初所在的楼层号以及他想去的楼层号。

输出

打印 n 行。在第 i 行中打印一个数字——第 i 个人到达他需要的楼层的时刻。人员按照输入中给出的顺序进行编号。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3 10
1 2 7
3 6 5
3 4 8

输出 #1

7
11
8

输入 #2

2 10
1 2 5
7 4 5

输出 #2

5
9

注意

在第一个示例中,电梯的工作原理如下:

- t = 1.电梯在1号楼。电梯是空的。 2号楼有一个人在等候。 pup = 1 + 0 = 1, pdown = 0 + 0 = 0, pup ≥ pdown。于是电梯就到了2号楼。
- t = 2,电梯在2号楼,一个人进入电梯,他想去7号楼。 pup = 0 + 1 = 1, pdown = 0 + 0 = 0, pup ≥ pdown。于是电梯就到了3楼。
- t = 3,电梯在3楼,电梯里有一个人,他想去7楼,4、6楼有两个人在等电梯。 pup = 2 + 1 = 3, pdown = 0 + 0 = 0, pup ≥ pdown。于是电梯就到了4楼。
- t = 4.电梯在4号楼。电梯里有一个人想去7号楼。一个人走进电梯,他想去8号楼。6号楼有一个人在等待。 pup = 1 + 2 = 3, pdown = 0 + 0 = 0, pup ≥ pdown。于是电梯就到了5楼。
- t = 5.电梯在5楼。电梯里有两个人,他们想分别去7楼和8楼。 6 楼有一个人在等电梯。 pup = 1 + 2 = 3, pdown = 0 + 0 = 0, pup ≥ pdown。于是电梯就到了6楼。
- t = 6.电梯在6楼。电梯里有两个人,他们想分别去7楼和8楼。一个人进入电梯,他想到达5楼。 pup = 0 + 2 = 2, pdown = 0 + 1 = 1, pup ≥ pdown。于是电梯就到了7楼。
- t = 7.电梯在7楼。一个人离开电梯,此人想去7楼。电梯里有两个人,他们想去相应的8楼和5楼。 pup = 0 + 1 = 1, pdown = 0 + 1 = 1, pup ≥ pdown。于是电梯就到了8号楼。
- t = 8.电梯在8号楼。一个人离开电梯,这个人想去8号楼。电梯里有一个人,他想去5号楼。 pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown。于是电梯就到了7楼。
- t = 9.电梯在7楼。电梯里有一个人,此人想去5楼。 pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown。于是电梯就到了6楼。
- t = 10.电梯在6号楼。电梯里有一个人,他想去5号楼。 pup = 0 + 0 = 0, pdown = 0 + 1 = 1, pup < pdown。于是电梯就到了5楼。
- t = 11.电梯在5号楼。一个人离开电梯,这个人最初想去5号楼。电梯是空的,没有人需要它,所以电梯停留在5号楼。