AtCoder-ABC212 D - Querying Multiset【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210731235323p:plain

AtCoder Beginner Contest212のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 212 - AtCoder

AtCoder Beginner Contest212 D - Querying Multiset

問題文

高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。最初、袋は空で、高橋君は Q 回の操作を行います。それぞれの操作は以下の 3 種類のうちのいずれかです。

・操作 1 : まだ何も書かれていないボール 1 つに整数 Xi を書き込み、袋に入れる。
・操作 2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それに Xi を加えたものに書き換える。
・操作 3 : 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの 1 つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。
1 ≤ i ≤ Q について i 回目の操作の種類 Pi および操作 1 , 2 における Xi の値が与えられるので、操作 3 において記録された数を順に出力してください。

制約

・1 ≤ Q ≤ 2×10^5
・1 ≤ Pi ≤ 3
・1 ≤ Xi ≤ 10^9
・入力は全て整数である。
・Pi=3 であるような i が 1 つ以上存在する。
・Pi=3 であるとき、 i 回目の操作の直前の時点で、袋には 1 つ以上のボールが入っている。

解答例

import heapq

q = int(input())

box = []
# boxを優先度付きキューに
heapq.heapify(box)

sum = 0
for i in range(q):
    Q = list(map(int, input().split()))
    if Q[0] == 1:
        heapq.heappush(box, Q[1]-sum)
    elif Q[0] == 2:
        sum += Q[1]
    else:
        tmp = heapq.heappop(box)
        print(tmp + sum)