3246. 实验室传染病

单点时限: 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
4
0 10
8 3
18 10
20 1
Output
2 1 3 1

46 人解决,178 人已尝试。

107 份提交通过,共有 852 份提交。

6.4 EMB 奖励。

创建: 3 年,3 月前.

修改: 2 年,11 月前.

最后提交: 8 月,3 周前.

来源: 2017 华东师范大学网赛

题目标签