結果

問題 No.649 ここでちょっとQK！
ユーザー るこーそーるこーそー
提出日時 2024-11-14 15:24:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,167 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 280,632 KB
最終ジャッジ日時 2024-11-14 15:25:43
合計ジャッジ時間 65,017 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
62,536 KB
testcase_01 AC 49 ms
60,160 KB
testcase_02 AC 42 ms
61,860 KB
testcase_03 AC 450 ms
224,568 KB
testcase_04 TLE -
testcase_05 AC 2,886 ms
280,632 KB
testcase_06 TLE -
testcase_07 AC 41 ms
56,680 KB
testcase_08 AC 39 ms
55,808 KB
testcase_09 AC 39 ms
55,792 KB
testcase_10 AC 41 ms
55,548 KB
testcase_11 AC 40 ms
56,216 KB
testcase_12 AC 2,984 ms
138,752 KB
testcase_13 AC 2,548 ms
136,332 KB
testcase_14 AC 2,647 ms
123,648 KB
testcase_15 AC 2,280 ms
134,976 KB
testcase_16 AC 2,560 ms
138,240 KB
testcase_17 AC 2,326 ms
142,288 KB
testcase_18 AC 2,718 ms
151,180 KB
testcase_19 AC 2,925 ms
157,088 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 162 ms
77,696 KB
testcase_28 AC 149 ms
77,232 KB
testcase_29 AC 167 ms
78,444 KB
testcase_30 AC 1,535 ms
91,664 KB
testcase_31 AC 1,412 ms
90,624 KB
testcase_32 AC 44 ms
54,912 KB
testcase_33 AC 40 ms
54,940 KB
testcase_34 AC 41 ms
54,656 KB
testcase_35 AC 41 ms
194,048 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import sys
sys.setrecursionlimit(10**5)

class Node:
    def __init__(self, v):
        self.v = v
        self.sum = v
        self.l = None
        self.r = None
        self.cnt = 1

class RBST:
    def __init__(self):
        self.root = None

    def size(self, t):
        return 0 if t is None else t.cnt

    def sum(self, t):
        return 0 if t is None else t.sum

    def update(self, t):
        if t:
            t.cnt = 1 + self.size(t.l) + self.size(t.r)
            t.sum = t.v + self.sum(t.l) + self.sum(t.r)
        return t

    def merge(self, l, r):
        if not l or not r:
            return r if not l else l
        if random.randint(0, self.size(l) + self.size(r) - 1) < self.size(l):
            l.r = self.merge(l.r, r)
            return self.update(l)
        else:
            r.l = self.merge(l, r.l)
            return self.update(r)

    def split(self, t, v):
        if not t:
            return None, None
        if v <= t.v:
            s1, s2 = self.split(t.l, v)
            t.l = s2
            return s1, self.update(t)
        else:
            s1, s2 = self.split(t.r, v)
            t.r = s1
            return self.update(t), s2

    def _insert(self, t, v):
        s1, s2 = self.split(t, v)
        n = Node(v)
        return self.merge(self.merge(s1, n), s2)

    def _erase(self, t, v):
        s1, s2 = self.split(t, v + 1)
        s3, _ = self.split(s1, v)
        return self.merge(s3, s2)

    def _discard(self, t, v):
        if not t:
            return None
        if v < t.v:
            t.l = self._discard(t.l, v)
        elif t.v < v:
            t.r = self._discard(t.r, v)
        else:
            return self.merge(t.l, t.r)
        return self.update(t)

    def _lower_bound(self, t, k):
        if not t:
            return 0
        if t.v < k:
            return self.size(t.l) + 1 + self._lower_bound(t.r, k)
        else:
            return self._lower_bound(t.l, k)

    def _upper_bound(self, t, k):
        if not t:
            return 0
        if t.v <= k:
            return self.size(t.l) + 1 + self._upper_bound(t.r, k)
        else:
            return self._upper_bound(t.l, k)

    def _get(self, t, k):
        s = self.size(t.l)
        if s > k:
            return self._get(t.l, k)
        elif s < k:
            return self._get(t.r, k - s - 1)
        else:
            return t.v

    def insert(self, v):
        self.root = self._insert(self.root, v)

    def erase(self, v):
        self.root = self._erase(self.root, v)

    def discard(self, v):
        self.root = self._discard(self.root, v)

    def get(self, k):
        return self._get(self.root, k)

    def lower_bound(self, k):
        return self._lower_bound(self.root, k)

    def upper_bound(self, k):
        return self._upper_bound(self.root, k)

    def __getitem__(self,k):
        return self.get(k)
      

rbst = RBST()
q ,k = map(int,input().split())
for i in range(q):
  query=list(map(int,input().split()))
  if query[0]==1:
    v=query[1]
    rbst.insert(v)
  else:
    if k<=rbst.size(rbst.root):
      print(rbst[k-1])
      rbst.discard(rbst[k-1])
    else:
      print(-1)
0