← 返回题目列表

Codeforces · 56/E

E. 多米诺骨牌原理

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

Vasya 对排列多米诺骨牌很感兴趣。他厌倦了普通的多米诺骨牌,他使用不同高度的多米诺骨牌。他沿着一个轴,从左到右,在桌子上放了n张多米诺骨牌。每块多米诺骨牌都垂直于该轴,因此该轴穿过其底座的中心。第 i 个多米诺骨牌的坐标为 xi,高度为 hi。现在,Vasya 想要了解每一张多米诺骨牌,如果他将其推向右侧,将会有多少张多米诺骨牌倒下。帮助他做到这一点。

考虑一下,如果多米诺骨牌严格接触底座上方,那么它就会倒下。换句话说,初始坐标为 x、高度为 h 的多米诺骨牌倒下,会导致线段 [x + 1, x + h - 1] 上的所有多米诺骨牌倒下。

输入

第一行包含整数 n (1 ≤ n ≤ 105),它是多米诺骨牌的数量。接下来的 n 行分别包含两个整数 xi 和 hi (- 108 ≤ xi ≤ 108, 2 ≤ hi ≤ 108),它们是每个多米诺骨牌的坐标和高度。没有两块多米诺骨牌会站在一个点上。

输出

打印 n 个空格分隔的数字 zi — 如果 Vasya 将第 i 个多米诺骨牌推向右侧(包括多米诺骨牌本身),将会倒下的多米诺骨牌数量。

示例

输入 #1

4
16 5
20 5
10 10
18 2

输出 #1

3 1 4 1

输入 #2

4
0 10
1 5
9 10
15 10

输出 #2

4 1 2 1