AT_abc221_d [ABC221D] Online games

题目描述

有一个在线游戏，有 $N$ 名玩家注册。
在距离服务开始日已经过去 $10^{100}$ 天的今天，开发者高桥君调查了登录记录，发现第 $i$ 个玩家从服务开始日的第 $A_i$ 天起，连续登录了 $B_i$ 天，除此之外没有登录。
也就是说，第 $i$ 个玩家仅在第 $A_i$、$A_i+1$、$\ldots$、$A_i+B_i-1$ 天登录。
请你对于每个满足 $1\leq k\leq N$ 的整数 $k$，计算从服务开始日到今天为止，恰好有 $k$ 人登录的天数。

输入格式

输入通过标准输入按以下格式给出。

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

请输出 $N$ 个整数，用空格隔开。

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

其中，$D_i$ 表示恰好有 $i$ 人登录的天数。

输入输出样例 #1

输入 #1

3
1 2
2 3
3 1

输出 #1

2 2 0

输入输出样例 #2

输入 #2

2
1000000000 1000000000
1000000000 1000000000

输出 #2

0 1000000000

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 10^9$
• $1\leq B_i\leq 10^9$
• 输入均为整数。

样例解释 1

第 $1$ 个玩家在第 $1$ 天和第 $2$ 天登录，第 $2$ 个玩家在第 $2$、$3$、$4$ 天登录，第 $3$ 个玩家只在第 $3$ 天登录。因此，第 $1$ 天和第 $4$ 天有 $1$ 人登录，第 $2$ 天和第 $3$ 天有 $2$ 人登录，其他天没有人登录。
所以，恰好 $1$ 人登录的天数为 $2$ 天，恰好 $2$ 人登录的天数为 $2$ 天，恰好 $3$ 人登录的天数为 $0$ 天。

样例解释 2

也可能存在 $2$ 人及以上的玩家在完全相同的期间登录的情况。

由 ChatGPT 4.1 翻译