結果

問題 No.945 YKC饅頭
コンテスト
ユーザー pekempey
提出日時 2019-12-08 00:15:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 470 ms / 2,000 ms
コード長 881 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 424 ms
コンパイル使用メモリ 81,872 KB
実行使用メモリ 85,304 KB
最終ジャッジ日時 2024-12-26 18:58:17
合計ジャッジ時間 18,999 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
N, M = map(int, input().split())

def merge(x, y):
  if x is None: return y
  return x

U = 1 << 18
seg = [None] * (U * 2)
for i in range(N + 1):
  seg[i + U] = i

for i in reversed(range(1, U)):
  seg[i] = merge(seg[i * 2], seg[i * 2 + 1])

def erase(k):
  k += U
  seg[k] = None
  while k > 1:
    k >>= 1
    seg[k] = merge(seg[k * 2], seg[k * 2 + 1])

def find(l):
  l += U
  r = 2*U - 1
  resl = None
  resr = None
  while l <= r:
    if l % 2 == 1:
      resl = merge(resl, seg[l])
      l += 1
    if r % 2 == 0:
      resr = merge(seg[r], resr)
      r -= 1
    l >>= 1
    r >>= 1
  return merge(resl, resr)

ans = defaultdict(int)

for _ in range(M):
  l, r, t = input().split()
  l = int(l) - 1
  r = int(r) - 1
  while True:
    l = find(l)
    if l > r: break
    ans[t] += 1
    erase(l)

print(ans['Y'], ans['K'], ans['C'])
0