D - Diversity of Scores Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋君が主催するコンテストに、1 から N までの番号が付けられた N 人の選手が参加しています。 このコンテストは各選手がその得点を競うものであり、現在の得点はどの選手も 0 点です。

未来予知の能力を持つ高橋君は、今から選手たちの得点がどのように変動するかを知っています。 具体的には、i=1,2,\dots,T について、今から i 秒後に選手 A_i の得点が B_i 点増加します。 逆に、それ以外に得点の変動はありません。

得点の多様性を好む高橋君は、各時点における選手たちの得点に何種類の値が現れるかを知りたがっています。 i=1,2,\dots,T それぞれについて、今から i+0.5 秒後の選手たちの得点には何種類の値が現れるか求めてください。

例えば、ある時点における選手たちの得点がそれぞれ 10,20,30,20 点であった場合、この時点での選手たちの得点には 3 種類の値が現れています。

制約

  • 1\leq N, T\leq 2\times 10^5
  • 1\leq A_i \leq N
  • 1\leq B_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1 B_1
A_2 B_2
\vdots
A_T B_T

出力

T 行出力せよ。 i\ (1\leq i \leq T) 行目には、今から i+0.5 秒後の選手たちの得点には何種類の値が現れるかを整数として出力せよ。

入力例 1

3 4
1 10
3 20
2 10
2 10

出力例 1

2
3
2
2

選手 1,2,3 の得点をこの順に並べた数列を S とします。 現在、S=\lbrace 0,0,0\rbrace です。

  • 1 秒後に選手 1 の得点が 10 点増加し、S=\lbrace 10,0,0\rbrace になります。よって、1.5 秒後の選手たちの得点には 2 種類の値が現れます。
  • 2 秒後に選手 3 の得点が 20 点増加し、S=\lbrace 10,0,20\rbrace になります。よって、2.5 秒後の選手たちの得点には 3 種類の値が現れます。
  • 3 秒後に選手 2 の得点が 10 点増加し、S=\lbrace 10,10,20\rbrace になります。よって、3.5 秒後の選手たちの得点には 2 種類の値が現れます。
  • 4 秒後に選手 2 の得点が 10 点増加し、S=\lbrace 10,20,20\rbrace になります。よって、4.5 秒後の選手たちの得点には 2 種類の値が現れます。

入力例 2

1 3
1 3
1 4
1 3

出力例 2

1
1
1

入力例 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

出力例 3

2
2
3
3
4
4
5
5
6
5

Score: 400 points

Problem Statement

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.

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.

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

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.

Sample Input 1

3 4
1 10
3 20
2 10
2 10

Sample Output 1

2
3
2
2

Let S be the sequence of scores of players 1, 2, 3 in this order. Currently, S=\lbrace 0,0,0\rbrace.

  • After one second, the score of player 1 increases by 10 points, making S=\lbrace 10,0,0\rbrace. 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=\lbrace 10,0,20\rbrace. 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=\lbrace 10,10,20\rbrace. 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=\lbrace 10,20,20\rbrace. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.

Sample Input 2

1 3
1 3
1 4
1 3

Sample Output 2

1
1
1

Sample Input 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Sample Output 3

2
2
3
3
4
4
5
5
6
5