10072: ABC343 —— D - Diversity of Scores
[Creator : ]
Description
Takahashi is hosting a contest with $N$ players numbered $1$ to $N$. The players will compete for points. Currently, all players have zero points.
Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for $i=1,2,\dots,T$, the score of player $A_i$ will increase by $B_i$ points at $i$ seconds from now. There will be no other change in the scores.
Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each $i=1,2,\dots,T$, find the number of different score values among the players' scores at $i+0.5$ seconds from now.
For example, if the players have $10$, $20$, $30$, and $20$ points at some moment, there are three different score values among the players' scores at that moment.
Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for $i=1,2,\dots,T$, the score of player $A_i$ will increase by $B_i$ points at $i$ seconds from now. There will be no other change in the scores.
Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each $i=1,2,\dots,T$, find the number of different score values among the players' scores at $i+0.5$ seconds from now.
For example, if the players have $10$, $20$, $30$, and $20$ points at some moment, there are three different score values among the players' scores at that moment.
Input
The input is given from Standard Input in the following format:
```
$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_T$ $B_T$
```
```
$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_T$ $B_T$
```
Output
Print $T$ lines. The $i$-th line $(1\leq i \leq T)$ should contain an integer representing the number of different score values among the players' scores at $i+0.5$ seconds from now.
Constraints
- $1\leq N, T\leq 2\times 10^5$
- $1\leq A_i \leq N$
- $1\leq B_i \leq 10^9$
- All input values are integers.
- $1\leq A_i \leq N$
- $1\leq B_i \leq 10^9$
- All input values are integers.
Sample 1 Input
3 4
1 10
3 20
2 10
2 10
Sample 1 Output
2
3
2
2
Let S be the sequence of scores of players 1,2,3 in this order. Currently, S={0,0,0}.
- After one second, the score of player 1 increases by 10 points, making S={10,0,0}. Thus, there are two different score values among the players' scores at 1.5 seconds from now.
- After two seconds, the score of player 3 increases by 20 points, making S={10,0,20}. Thus, there are three different score values among the players' scores at 2.5 seconds from now.
- After three seconds, the score of player 2 increases by 10 points, making S={10,10,20}. Therefore, there are two different score values among the players' scores at 3.5 seconds from now.
- After four seconds, the score of player 2 increases by 10 points, making S={10,20,20}. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.
Sample 2 Input
1 3
1 3
1 4
1 3
Sample 2 Output
1
1
1
Sample 3 Input
10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225
Sample 3 Output
2
2
3
3
4
4
5
5
6
5