← 返回题目列表

AtCoder · codefestival_2015_qualB_d

D. 方块、碎片和着色

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

问题陈述

10^{100} 方块排成一排。方块已编号 1 通过 10^{100} 从左到右。

我们有 N 件编号 1 通过 N, 和一个可以存储整数的计数器 0 和 10^{100}, 包括在内。

我们将表演 N 使用这些工具进行处理。最初,正方形被漆成白色。 i^{th} (1≦i≦N) 流程如下:

  1. 放置棋子 i 在广场上 S_i,并将计数器设置为 0.
  2. 看方块的颜色 已放置 i 。如果正方形是白色的,则将其涂成黑色并将计数器增加 1。否则(如果方块是黑色),移动棋子 i 右边一格。因此,一个正方形可能包含多个棋子。
  3. 如果计数器的值为 C_i. 否则,返回步骤 2.

找到每个的最终位置 N 件毕竟 N 进程。


输入

输入由标准输入按以下格式给出:

N
S_1 C_1
S_2 C_2
:
S_N C_N
  • 第一行包含一个整数 N (1 ≦ N ≦ 10^5).
  • 以下 N 行描述了这些过程。 其中 i^{th} (1 ≦ i ≦ N) 包含两个空格分隔的整数 S_i (1 ≦ S_i ≦ 10^9) 和 C_i (1≦C_i≦10^9), 表示棋子的初始位置 i 在 i^{th} 进程及终止条件 i^{th} 分别处理。

部分积分

此问题可能会获得部分分数:

  • 35 分:经过所有过程后,每个棋子所在的方格数不超过 10^5.
  • 另一个 通过满足以下条件的测试集将获得 40 积分 在没有额外限制的情况下通过测试集将获得 N ≦ 1000.
  • 另一个 通过满足以下条件的测试集将获得 25 分。

输出

打印 N 行, i^{th} (1≦i≦N) 其中应包含棋子所在方格的编号 i 位于所有 N 进程。确保在输出末尾打印换行符。


示例输入 1

4
3 3
10 1
4 2
2 4

示例输出 1

5
10
7
11

下图是每道工序后方块和棋子的状态:

figure1

示例输入 2

8
2 1
3 1
1 1
5 1
1 1
9 1
8 2
7 9

示例输出 2

2
3
1
5
4
9
10
18

示例输入 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

示例输出 3

1999999999
2999999999
3999999999
4999999999
5999999999

请注意,正确的输出可能不适合 32位整数。