結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2018-02-11 17:19:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,133 ms / 3,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 20,096 KB |
最終ジャッジ日時 | 2024-11-17 06:59:33 |
合計ジャッジ時間 | 16,938 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#!/usr/bin/env python3 import heapq INVALID = -1 class Solver(object): def __init__(self, k): self.k = k # 最小からK個までの要素を格納する最大ヒープ # 実装上は最小ヒープ+負数で代用 self.max_heap = [] # 残りの要素を格納する最小ヒープ self.min_heap = [] def parse_query1(self, v): if len(self.max_heap) < self.k: heapq.heappush(self.max_heap, -v) else: m1 = -self.max_heap[0] if m1 <= v: heapq.heappush(self.min_heap, v) else: _ = heapq.heappop(self.max_heap) heapq.heappush(self.min_heap, m1) heapq.heappush(self.max_heap, -v) def parse_query2(self): if len(self.max_heap) < self.k: return INVALID else: res = -heapq.heappop(self.max_heap) if self.min_heap: heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) return res def main(): q, k = (int(z) for z in input().split()) solver = Solver(k) for _ in range(q): args = [int(z) for z in input().split()] if args[0] == 1: solver.parse_query1(args[1]) else: print(solver.parse_query2()) if __name__ == '__main__': main()