ABC253 C - Max - Min Query
提出
code: python
from collections import defaultdict
q = int(input())
d = defaultdict(int)
minmax = set()
for query in queries:
res = min(d[query1], query2) else:
print(max(minmax) - min(minmax))
解答
code: python
from collections import defaultdict
import heapq
q = int(input())
d = defaultdict(int)
maxq = []
minq = []
for query in queries:
heapq.heappush(minq, query1) # heapqは最小値しか取り出せないから-を掛ける
heapq.heappush(maxq, -query1) d[query1] -= min(query2 , d[query1]) else:
qmin = heapq.heappop(minq)
# 次の最小値を取り出す
qmin = heapq.heappop(minq)
qmax = heapq.heappop(maxq)
qmax *= -1
# 次の最大値を取り出す
qmax = heapq.heappop(maxq)
qmax *= -1
print(qmax-qmin)
# 最小値、最大値をheapq へ戻す
heapq.heappush(minq,qmin)
heapq.heappush(maxq,-qmax)
テーマ
メモ