ABC221D - Online games

考え方

差分だけを処理していく問題．ログインとログアウトを後で区別できるようにして「ごちゃまぜソート」をするとラク（これもよくあるパターン）．

日付を1日単位で見るとTLE．「現れる日付の差」を使って処理する．

現れる日付を前から見ていき，今ログインしている人数cntを管理する．ログイン人数がcntのときの答えをans[cnt]とする．

1. （前日-最終変化日+1）＝（当日-最終変化日）をans[cnt]に加える．
2. ログインならcntに1を加え，ログアウトなら1を引く．
3. 最終変化日last更新する．

回答例

N = int(input())
L = []
for _ in range(N):
  A, B = map(int, input().split())
  L.append((A, 1))
  L.append((A + B, -1))
  
L.sort()
last = 0
cnt = 0
ans = [0] * (N + 1)
for X in L:
  ans[cnt] += X[0] - last
  cnt += X[1]
  last = X[0]
    
print(*ans[1:])