Score : $400$ points

问题描述

存在一款拥有 $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$ 名玩家登录的天数。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:45:09