ABC253 C - Max - Min Query
https://atcoder.jp/contests/abc253/tasks/abc253_c
提出
code: python
from collections import defaultdict
q = int(input())
queries = list(map(int, input().split())) for _ in range(q)
d = defaultdict(int)
minmax = set()
for query in queries:
#print(minmax)
if (query0 == 1):
d[query1] += 1
minmax.add(query1)
elif (query0 == 2):
res = min(d[query1], query2)
if (res == d[query1]):
minmax.discard(query1)
d[query1] -= res
else:
print(max(minmax) - min(minmax))
解答
code: python
from collections import defaultdict
import heapq
q = int(input())
queries = list(map(int, input().split())) for _ in range(q)
d = defaultdict(int)
maxq = []
minq = []
for query in queries:
if query0 == 1:
d[query1] += 1
heapq.heappush(minq, query1)
# heapqは最小値しか取り出せないから-を掛ける
heapq.heappush(maxq, -query1)
elif query0 == 2:
d[query1] -= min(query2 , d[query1])
else:
qmin = heapq.heappop(minq)
while dqmin == 0:
# 次の最小値を取り出す
qmin = heapq.heappop(minq)
qmax = heapq.heappop(maxq)
qmax *= -1
while dqmax == 0:
# 次の最大値を取り出す
qmax = heapq.heappop(maxq)
qmax *= -1
print(qmax-qmin)
# 最小値、最大値をheapq へ戻す
heapq.heappush(minq,qmin)
heapq.heappush(maxq,-qmax)
テーマ
#heapq
メモ
https://atcoder.jp/contests/abc253/submissions/32136208