← 返回题目列表

AtCoder · abc221_d

G. 网络游戏

中文机器翻译题面 查看原题

分数: 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

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