Problem #3246 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

ECNU 的 ACM 实验室患上了一种传染病，这种病的传染性极强，并且因为每个人的体质不同传染的范围也不同。

为了简化这个问题，我们不妨假设有 $n$ 个人站在一条水平线上，每个人有初始的位置和他患病时的传染范围。当一个人患病时，他的传染范围内（包括边界上）的人全部会被感染并继续向外传播。

但是我们并不知道 ECNU 实验室的传染源是谁，所以请你计算出每个人作为传染源时最后会使得多少人被感染？

测试数据包含不超过 20 个测试文件，每个测试文件是单组数据。

第一行一个整数 $n$ $(1 \leq n \leq 10^{5})$ 。

接下来 $n$ 行每行有两个整数 $x_{i}, r_{i}$ $(- 10^{9} \leq x_{i} \leq 10^{9} ， 1 \leq r_{i} \leq 10^{9})$ ，表示每个人的位置和传染范围。

数据保证位置各不相同。

一行 $n$ 个整数。其中第 $i$ 个表示第 $i$ 个人（按照输入顺序）作为传染源时最后被感染的人数。

Input

Output

2 1 3 1

49 人解决，184 人已尝试。

111 份提交通过，共有 870 份提交。

6.3 EMB 奖励。

创建: 7 年，10 月前.

修改: 7 年，7 月前.

最后提交: 1 周，6 天前.

3246. 实验室传染病