ABC343 D - Diversity of Scores

atcoder.jp

問題

• N人の選手がコンテストに参加するよ。みんな最初は0点だよ
• 今から$i$秒後に、選手$A_i$が、$B_i$点増加するよ
• $i+0.5$秒後に、選手たちの得点は何種類？

成約

• $1 \leq N,T \leq 2 \times 10^{5}$
• $1 \leq B_i \leq 10^{9}$

思考

• 大人しくシミュレーションしていくけど、毎秒全員の点数を確認するのは間に合わないので…
• それぞれの選手の「今何点？」と、「◯点の選手は今何人？」を持って更新していく

コード

N,T = map(int,input().split())

score_L = [0]*N
score_d = defaultdict(int)
score_d[0] = N

for _ in range(T):
    A,B = map(int,input().split())
    A -= 1

    score_d[score_L[A]] -= 1
    if score_d[score_L[A]] == 0:
        score_d.pop(score_L[A])

    score_L[A] += B
    score_d[score_L[A]] += 1