提出 #69958477

---

ソースコード 拡げる

"""
<方針>
- 毎クエリ `O(Q)` で全てのPCのバージョンを見て `O(N)` しまうと、`O(NQ)` で間に合わない。
- PCのバージョンがそれぞれ何個あるか `versions` を持たせる。
- 常に最低バージョンが何か `mi` を保持させておけば、毎クエリ `N` 個も見ることはない。
- したがって、全体として、`O(N+Q)` で処理できる。
"""
N, Q = map(int, input().split())

# i番目のバージョンを持つPCはいくつあるか。
versions = [1]*N

# 存在する最低バージョン
mi = 0

for _ in range(Q):
  X, Y = map(int, input().split())
  X -= 1
  Y -= 1
  
  # 更新するPCの個数をカウント
  ans = 0
  # 最低バージョンからループさせれば、間に合う。
  for i in range(mi, X+1):
    ans += versions[i]
    versions[i] = 0 # ここはコメントアウトしても多分通る。
  
  # 個数を変える
  versions[Y] += ans
  
  # PCを更新できたら、そのバージョンが最低バージョンとなる。
  if(ans > 0):
    mi = X+1
  
  # 出力
  print(ans)

提出情報

ジャッジ結果