/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
あるオンラインゲームがあり、
N 人のプレイヤーが登録しています。
サービス開始日から 10^{100} 日を迎えた今日、
開発者である高橋君がログイン履歴を調べたところ、
i 番目のプレイヤーはサービス開始日を 1 日目として、
A_i 日目から B_i 日間連続でログインし、
それ以外の日はログインしていなかったことが判明しました。
すなわち、i 番目のプレイヤーはサービス開始日から、A_i , A_i+1 , \ldots , A_i+B_i-1 日目に、
かつそれらの日にのみログインしていたことが分かりました。
1\leq k\leq N をみたす各整数 k について、
サービス開始日から今日までの間で、ちょうど 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 はちょうど i 人がゲームにログインしていた日数を表す。
入力例 1
3 1 2 2 3 3 1
出力例 1
2 2 0
1 番目のプレイヤーは 1 日目と 2 日目に、 2 番目のプレイヤーは 2 日目と 3 日目と 4 日目に、 3 番目のプレイヤーは 3 日目だけにログインしています。 よって、1, 4 日目には 1 人が、2, 3 日目には 2 人がログインしており、 それ以外の日は誰もログインしていない事が分かります。 答えはちょうど 1 人がログインした日数が 2 日、 ちょうど 2 人がログインした日数が 2 日、 ちょうど 3 人がログインした日数が 0 日となります。
入力例 2
2 1000000000 1000000000 1000000000 1000000000
出力例 2
0 1000000000
2 人以上のプレイヤーがちょうど同じ期間にログインしていることもあり得ます。
Score : 400 points
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.