結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2025-03-10 04:55:57 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,892 bytes |
コンパイル時間 | 597 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 107,604 KB |
最終ジャッジ日時 | 2025-03-10 04:56:46 |
合計ジャッジ時間 | 47,825 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 TLE * 2 |
ソースコード
import random class RBST: class Node: def __init__(self, val): self.val = val self.left = None self.right = None self.size = 1 self.sum = val def update(self): pass def push(self): pass def __init__(self, node: Node = None): self.root = node def __len__(self): return RBST.size(self.root) @staticmethod def size(node: Node) -> int: if node is None: return 0 return node.size @staticmethod def update(node: Node) -> Node: node.size = RBST.size(node.left) + RBST.size(node.right) + 1 node.update() return node @staticmethod def push(node: Node): if node is None: return node.push() @staticmethod def _lower_bound(node: Node, val): RBST.push(node) if node is None: return 0 if val <= node.val: return RBST._lower_bound(node.left, val) else: return RBST.size(node.left) + RBST._lower_bound(node.right, val) + 1 def lower_bound(self, val): return RBST._lower_bound(self.root, val) @staticmethod def _upper_bound(node: Node, val): RBST.push(node) if node is None: return 0 if val >= node.val: return RBST.size(node.left) + RBST._upper_bound(node.right, val) + 1 else: return RBST._upper_bound(node.left, val) def upper_bound(self, val): return RBST._upper_bound(self.root, val) def count(self, val): return self.upper_bound(val) - self.lower_bound(val) @staticmethod def _get(node: Node, k: int): RBST.push(node) if node is None: return -1 if k == RBST.size(node.left): return node.val if k < RBST.size(node.left): return RBST._get(node.left, k) else: return RBST._get(node.right, k - RBST.size(node.left) - 1) def get(self, k): return RBST._get(self.root, k) @staticmethod def _merge(left: Node, right: Node): RBST.push(left) RBST.push(right) if left is None or right is None: if left: return left else: return right r = random.randint(1, 0xfffffff) if r % (left.size + right.size) < left.size: left.right = RBST._merge(left.right, right) return RBST.update(left) else: right.left = RBST._merge(left, right.left) return RBST.update(right) def merge(self, add): self.root = RBST._merge(self.root, add.root) @staticmethod def _split(node: Node, k: int) -> tuple[Node, Node]: # [0, k), [k, n) RBST.push(node) if node is None: return node, node if k <= RBST.size(node.left): a, b = RBST._split(node.left, k) node.left = b return a, RBST.update(node) else: a, b = RBST._split(node.right, k - RBST.size(node.left) - 1) node.right = a return RBST.update(node), b def split(self, k: int): a, b = RBST._split(self.root, k) self.root = a return RBST(b) def insert(self, val): a, b = RBST._split(self.root, self.lower_bound(val)) self.root = RBST._merge(RBST._merge(a, RBST.Node(val)), b) def erase(self, val): if self.count(val) == 0: return a, b = RBST._split(self.root, self.lower_bound(val)) _, r = RBST._split(b, 1) self.root = RBST._merge(a, r) Q, K = map(int, input().split()) st = RBST() for _ in range(Q): qs = list(map(int, input().split())) if qs[0] == 1: v = qs[1] st.insert(v) elif qs[0] == 2: if len(st) < K: print(-1) else: res = st.get(K-1) print(res) st.erase(res)