結果
問題 | No.649 ここでちょっとQK! |
ユーザー | toyuzuko |
提出日時 | 2020-06-06 12:30:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,643 ms / 3,000 ms |
コード長 | 4,480 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 86,796 KB |
実行使用メモリ | 101,132 KB |
最終ジャッジ日時 | 2023-08-25 00:28:31 |
合計ジャッジ時間 | 24,969 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,040 KB |
testcase_01 | AC | 72 ms
71,168 KB |
testcase_02 | AC | 72 ms
71,168 KB |
testcase_03 | AC | 144 ms
87,288 KB |
testcase_04 | AC | 244 ms
94,972 KB |
testcase_05 | AC | 329 ms
97,424 KB |
testcase_06 | AC | 245 ms
94,156 KB |
testcase_07 | AC | 73 ms
71,156 KB |
testcase_08 | AC | 71 ms
71,184 KB |
testcase_09 | AC | 71 ms
71,312 KB |
testcase_10 | AC | 71 ms
71,516 KB |
testcase_11 | AC | 71 ms
71,436 KB |
testcase_12 | AC | 895 ms
90,356 KB |
testcase_13 | AC | 887 ms
91,236 KB |
testcase_14 | AC | 882 ms
90,456 KB |
testcase_15 | AC | 983 ms
91,772 KB |
testcase_16 | AC | 945 ms
91,344 KB |
testcase_17 | AC | 990 ms
90,956 KB |
testcase_18 | AC | 1,104 ms
93,616 KB |
testcase_19 | AC | 1,192 ms
96,176 KB |
testcase_20 | AC | 1,223 ms
97,304 KB |
testcase_21 | AC | 1,335 ms
99,944 KB |
testcase_22 | AC | 1,342 ms
96,948 KB |
testcase_23 | AC | 1,453 ms
100,524 KB |
testcase_24 | AC | 1,480 ms
100,852 KB |
testcase_25 | AC | 1,556 ms
99,992 KB |
testcase_26 | AC | 1,643 ms
101,132 KB |
testcase_27 | AC | 168 ms
77,764 KB |
testcase_28 | AC | 191 ms
78,208 KB |
testcase_29 | AC | 194 ms
78,224 KB |
testcase_30 | AC | 937 ms
92,084 KB |
testcase_31 | AC | 1,022 ms
93,276 KB |
testcase_32 | AC | 71 ms
71,516 KB |
testcase_33 | AC | 71 ms
70,972 KB |
testcase_34 | AC | 70 ms
71,108 KB |
testcase_35 | AC | 70 ms
71,380 KB |
ソースコード
class SplayNode(): def __init__(self, val): self.val = val self.par = None self.lt = None self.rt = None self.size = 1 class SplayTree(): def __init__(self): self.size = 0 self.root = None def update(self, node): node.size = 1 if node.lt is not None: node.size += node.lt.size if node.rt is not None: node.size += node.rt.size def rotate(self, node): par = node.par if par is None: return ppar = par.par if par.lt == node: rt = node.rt par.lt = rt par.par = node node.rt = par self.update(par) self.update(node) if rt is not None: rt.par = par node.par = ppar if ppar is None: return if ppar.lt == par: ppar.lt = node else: ppar.rt = node else: lt = node.lt par.rt = lt par.par = node node.lt = par self.update(par) self.update(node) if lt is not None: lt.par = par node.par = ppar if ppar is None: return if ppar.rt == par: ppar.rt = node else: ppar.lt = node def splay(self, node): while node.par is not None: self.rotate(node) self.size = node.size self.root = node def get(self, k): node = self.root if self.size <= k: return False while True: lsize = 0 if node.lt is None else node.lt.size if lsize == k: self.splay(node) return node if lsize > k: node = node.lt else: k -= lsize + 1 node = node.rt def find(self, val): node = self.root if node is None: return False, 0 count = 0 while True: lsize = 0 if node.lt is None else node.lt.size if node.val == val: self.splay(node) return True, count + lsize if node.val > val: if node.lt is None: return False, count + lsize else: node = node.lt else: if node.rt is None: return False, count + lsize + 1 else: count += lsize + 1 node = node.rt def merge(self, other): if self.size == 0: self.size = other.size self.root = other.root return if other.size == 0: return lnode = self.get(self.size - 1) rnode = other.get(0) rnode.par = lnode lnode.rt = rnode self.update(lnode) self.root = lnode self.size = lnode.size def split(self, k): other = SplayTree() if k == 0: other.root = self.root other.size = self.size self.size = 0 self.root = None return other if k == self.size: return other root = self.get(k) lroot = root.lt rroot = root rroot.lt = None lroot.par = None self.update(lroot) self.update(rroot) self.size = lroot.size self.root = lroot other.size = rroot.size other.root = rroot return other def insert(self, val): _, k = self.find(val) rtree = self.split(k) nnode = SplayNode(val) ntree = SplayTree() ntree.root = nnode ntree.size = 1 self.merge(ntree) self.merge(rtree) def delete(self, val): exist, k = self.find(val) if not exist: return rtree = self.split(k + 1) deleted = self.split(k) self.merge(rtree) import sys input = sys.stdin.readline Q, K = map(int, input().split()) st = SplayTree() res = [] for _ in range(Q): q = tuple(map(int, input().split())) if q[0] == 1: st.insert(q[1]) else: v = st.get(K - 1) if not v: res.append(-1) else: res.append(v.val) st.delete(v.val) print('\n'.join(map(str, res)))