分数: 400 点
问题陈述
有一个在线游戏 N 注册玩家。
今天,这是 10^{100}自推出以来的第三天,开发人员 Takahashi 检查了用户的登录历史记录。事实证明, i第一个玩家登录的时间 B_i 从 Day 开始的连续天 A_i,其中日 1 为上线日,其他日子均未登录。
换句话说, i当天登录的玩家 A_i, A_i+1, \ldots, A_i+B_i-1,并且仅限那些日子。
对于每个整数 k 这样 1\leq k\leq N,找出恰好发生的天数 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 有玩家登录,其他日子没有玩家登录。
答案是:有 2 天与 1 玩家已登录, 2 天与 2 玩家已登录,并且 0 天与 3 玩家已登录。
示例输入 2
2 1000000000 1000000000 1000000000 1000000000
示例输出 2
0 1000000000
可能有两个或更多玩家在同一时间段内登录。