AtCoder Beginner Contest 212 [ D - Querying Multiset ] https://atcoder.jp/contests/abc212/tasks/abc212_d

abc212_d.py

'''
[問題]
https://atcoder.jp/contests/abc212/tasks/abc212_d

[解説]
https://blog.hamayanhamayan.com/entry/2021/08/01/012059

[参考]
【Python】優先度付きキューの使い方【heapq】【ABC141 D】
https://qiita.com/ell/items/fe52a9eb9499b7060ed6
'''

import sys
import heapq

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

f = []      # 袋のf
offset = 0

Q = int(input())

for _ in range(Q):
    q = list(map(int, input().split()))

    if q[0] == 1:
        # 袋に玉を追加。追加の際にoffset分ずらす
        heapq.heappush(f, q[1] - offset)
    elif q[0] == 2:
        # 全体にq[1]を足す
        offset += q[1]
    else:
        # 3
        # 最小値を取得
        m = heapq.heappop(f)
        print(m + offset)