2022/06/26 ABC253C

ABC253 C - Max - Min Query

atcoder.jp

2*10⁵個のクエリにおいて，最大値・最小値をheapqで高速に求める．

import heapq
from collections import defaultdict

Q = int(input())

Max_S = []
Min_S = []

S = defaultdict(int)

for i in range(Q):
    query = list(map(int, input().split()))
    op = query[0]
    if op == 1:
        op, x = query
        S[x] += 1
        heapq.heappush(Max_S, -x)
        heapq.heappush(Min_S, x)

    elif op == 2:
        op, x, c = query
        if S[x] > c:
            S[x] -= c
        else:
            S[x] = 0
    else:
        while S[-Max_S[0]] == 0:
            heapq.heappop(Max_S)
        while S[Min_S[0]] == 0:
            heapq.heappop(Min_S)
        print(-Max_S[0] - Min_S[0]) 

メモ

• Maxheap，Minheapを別々で求めても，制限時間内に求まる
• C++だと，Multisetなるもので，瞬殺できるらしい．
  • ずるくない?
• dequeとheapqがごちゃごちゃになっていた
  • あとで自分用のまとめ記事作る