結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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