Diversity of Scores

题目描述

Takahashi 正在举办一个有编号为 $1$ 到 $N$ 的 $N$ 名选手的比赛。 选手们将为积分而竞争。目前，所有选手的积分都为零。 Takahashi 的预见能力让他知道选手们的分数将如何变化。具体来说，对于 $i=1,2,\dots,T$，在 $i$ 秒之后，选手 $A_i$ 的分数将增加 $B_i$ 点。除此之外不会有其他分数变化。 Takahashi 喜欢分数的多样性，他想知道在每个时刻选手分数中会出现多少种不同的分数值。对于每个 $i=1,2,\dots,T$，求在 $i+0.5$ 秒之后选手分数中不同分数值的个数。 例如，如果某时刻选手的分数为 $10,20,30,20$，那么该时刻选手分数中有三种不同的分数值。

输入格式

输入按下列格式从标准输入给出： $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$ 秒之后选手分数中不同分数值的个数。

3 4
1 10
3 20
2 10
2 10

2
3
2
2

1 3
1 3
1 4
1 3

1
1
1

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

2
2
3
3
4
4
5
5
6
5

提示

$1\leq N, T\leq 2\times 10^5$ $1\leq A_i \leq N$ $1\leq B_i \leq 10^9$ 所有输入值均为整数。设 $S$ 为选手 $1,2,3$ 的分数组成的序列，按此顺序。 当前，$S=\lbrace 0,0,0\rbrace$。

一秒后，选手 $1$ 的分数增加 $10$ 点，使得 $S=\lbrace 10,0,0\rbrace$。因此，在 $1.5$ 秒之后选手分数中有两种不同的分数值。 两秒后，选手 $3$ 的分数增加 $20$ 点，使得 $S=\lbrace 10,0,20\rbrace$。因此，在 $2.5$ 秒之后选手分数中有三种不同的分数值。 三秒后，选手 $2$ 的分数增加 $10$ 点，使得 $S=\lbrace 10,10,20\rbrace$。因此，在 $3.5$ 秒之后选手分数中有两种不同的分数值。 四秒后，选手 $2$ 的分数增加 $10$ 点，使得 $S=\lbrace 10,20,20\rbrace$。因此，在 $4.5$ 秒之后选手分数中有两种不同的分数值。

标签: AtCoder|abc343D

来源

AtCoder|abc343D