Online games

题目描述

有一个有 $N$ 名注册玩家的在线游戏。
今天是自上线以来的第 $10^{100}$ 天，开发者 Takahashi 检查了用户的登录记录。结果表明，第 $i$ 位玩家从第 $A_i$ 天起连续登录了 $B_i$ 天，其中第 1 天为上线当天，其他天没有登录。 换言之，第 $i$ 位玩家在第 $A_i$、$A_i+1$、…、$A_i+B_i-1$ 天登录，仅在这些天登录。
对于每个整数 $k$ 且 $1\leq k\leq N$，求恰好有 $k$ 名玩家登录的天数。

输入格式

输入以标准输入给出，格式如下： $N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

输出格式

输出 $N$ 个用空格分隔的整数，如下所示： $D_1$ $D_2$ $\cdots$ $D_N$

这里，$D_i$ 表示恰好有 $k$ 名玩家登录的天数。

3
1 2
2 3
3 1

2 2 0

2
1000000000 1000000000
1000000000 1000000000

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、2 天登录，第 2 位玩家在第 2、3、4 天登录，第 3 位玩家仅在第 3 天登录。 因此，可以看到第 1、4 天有 1 名玩家登录，第 2、3 天有 2 名玩家登录，其他天没有玩家登录。 答案是：恰有 1 名玩家登录的天数为 2，恰有 2 名玩家登录的天数为 2，恰有 3 名玩家登录的天数为 0。
可能有两位或更多玩家在相同期间登录。

标签: AtCoder|abc221D

来源

AtCoder|abc221D