102213: [AtCoder]ABC221 D - Online games

Problem Statement

There is an online game with $N$ registered players.
Today, which is the $10^{100}$-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the $i$-th player logged in for $B_i$ consecutive days from Day $A_i$, where Day $1$ is the launch day, and did not log in for the other days. In other words, the $i$-th player logged in on Day $A_i$, $A_i+1$, $\ldots$, $A_i+B_i-1$, and only on those days.
For each integer $k$ such that $1\leq k\leq N$, find the number of days on which exactly $k$ players logged in.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$

Output

Print $N$ integers with spaces in between, as follows:

$D_1$ $D_2$ $\cdots$ $D_N$

Here, $D_i$ denotes the number of days on which exactly $k$ players logged in.

Sample Input 1

3
1 2
2 3
3 1

Sample Output 1

2 2 0

The first player logged in on Day $1$, $2$, the second player logged in on Day $2$, $3$, $4$, and the third player logged in on Day $3$ only.

Thus, we can see that Day $1$, $4$ had $1$ player logged in, Day $2$, $3$ had $2$ players logged in, and the other days had no players logged in.

The answer is: there were $2$ days with exactly $1$ player logged in, $2$ days with exactly $2$ players logged in, and $0$ days with exactly $3$ players logged in.

Sample Input 2

2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0 1000000000

There may be two or more players who logged in during the same period.

问题描述

有一个注册玩家为$N$的在线游戏。今天是该游戏发行的第$10^{100}$天，开发者高桥检查了用户的登录记录。发现第$i$个玩家从第$A_i$天开始连续登录了$B_i$天，其中第1天为发行日，其他日子没有登录。换句话说，第$i$个玩家在第$A_i$天、$A_i+1$天、$\ldots$、$A_i+B_i-1$天登录，仅在这些天登录。

对于满足$1\leq k\leq N$的每个整数$k$，找出恰好有$k$个玩家登录的天数。

限制条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$

输出

以空格分隔的方式打印$N$个整数，如下所示：

$D_1$ $D_2$ $\cdots$ $D_N$

其中$D_i$表示恰好有$k$个玩家登录的天数。

样例输入1

3
1 2
2 3
3 1

样例输出1

2 2 0

第一个玩家在第1天、2天登录，第二个玩家在第2天、3天、4天登录，第三个玩家仅在第3天登录。

因此，我们可以看到第1天、4天有1个玩家登录，第2天、3天有2个玩家登录，其他天数没有玩家登录。

答案是：恰好有1个玩家登录的天数为2天，恰好有2个玩家登录的天数为2天，恰好有3个玩家登录的天数为0天。

样例输入2

2
1000000000 1000000000
1000000000 1000000000

样例输出2

0 1000000000

可能存在两个或多个玩家在同一时间段内登录。