結果

問題 No.649 ここでちょっとQK！
ユーザー FuyuruFuyuru
提出日時 2024-01-23 13:26:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,043 ms / 3,000 ms
コード長 4,882 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 110,720 KB
最終ジャッジ日時 2024-09-28 06:43:32
合計ジャッジ時間 16,877 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,784 KB
testcase_01 AC 45 ms
54,912 KB
testcase_02 AC 45 ms
55,168 KB
testcase_03 AC 133 ms
77,440 KB
testcase_04 AC 348 ms
102,272 KB
testcase_05 AC 368 ms
102,144 KB
testcase_06 AC 371 ms
98,236 KB
testcase_07 AC 46 ms
54,784 KB
testcase_08 AC 44 ms
54,656 KB
testcase_09 AC 45 ms
54,784 KB
testcase_10 AC 44 ms
55,040 KB
testcase_11 AC 44 ms
55,040 KB
testcase_12 AC 474 ms
91,436 KB
testcase_13 AC 488 ms
91,468 KB
testcase_14 AC 491 ms
91,264 KB
testcase_15 AC 511 ms
92,272 KB
testcase_16 AC 474 ms
92,544 KB
testcase_17 AC 586 ms
94,976 KB
testcase_18 AC 605 ms
96,492 KB
testcase_19 AC 679 ms
97,920 KB
testcase_20 AC 702 ms
99,712 KB
testcase_21 AC 767 ms
101,768 KB
testcase_22 AC 847 ms
103,296 KB
testcase_23 AC 888 ms
105,148 KB
testcase_24 AC 958 ms
106,752 KB
testcase_25 AC 1,005 ms
109,824 KB
testcase_26 AC 1,043 ms
110,720 KB
testcase_27 AC 80 ms
70,588 KB
testcase_28 AC 82 ms
70,016 KB
testcase_29 AC 83 ms
70,784 KB
testcase_30 AC 501 ms
91,908 KB
testcase_31 AC 510 ms
92,364 KB
testcase_32 AC 47 ms
54,912 KB
testcase_33 AC 48 ms
54,784 KB
testcase_34 AC 51 ms
54,784 KB
testcase_35 AC 49 ms
54,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()
import random

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

    def __len__(self):
        if not self.root:
            return 0
        return self.root[3]

    # find a node with a key x
    def find(self, x):
        node = self.root
        while node:
            v = node[2]
            if v == x:
                return 1
            node = node[v < x]
        return 0

    # find the k-th key in a tree
    def __getitem__(self, k):
        node = self.root
        k += 1
        while 1:
            v = (node[0][3]+1 if node[0] else 1)
            if v == k:
                return node[2]
            if k < v:
                node = node[0]
            else:
                k -= v
                node = node[1]

    # insert a node with a key x
    def insert(self, x):
        # before insert(x), the tree must not contain a key x
        rand = random.random
        new_node = [None, None, x, 1]
        if not self.root:
            self.root = new_node
            return
        node = self.root
        prv = None
        while node:
            if node[3] == int(rand() * (node[3]+1)):
                break
            node[3] += 1
            prv = node
            node = node[node[2] < x]
        if prv:
            prv[prv[2] < x] = new_node
        else:
            self.root = new_node

        left = right = new_node
        st = []
        while node:
            st.append(node)
            if node[2] < x:
                left[1] = left = node
                node = node[1]
            else:
                right[0] = right = node
                node = node[0]
        left[1] = right[0] = None
        new_node[0], new_node[1] = new_node[1], new_node[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1
        l, r = new_node[:2]
        new_node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

    def build(self, A):
        for x in A:
            self.insert(x)

    # remove a node with key x
    def remove(self, x):
        # before remove(x), the tree must contain a key x
        rand = random.random
        node = self.root
        prt = None
        while node[2] != x:
            node[3] -= 1
            prt = node
            node = node[node[2] < x]

        cur = top = prt
        if prt:
            prv_d = (prt[1] == node)
        else:
            cur = top = [None]
            prv_d = 0
        left, right = node[:2]
        st = []; push = st.append
        while left and right:
            a = left[3]; b = right[3]
            if int(rand() * (a+b)) < a:
                push(left)
                cur[prv_d] = cur = left
                left = left[1]
                prv_d = 1
            else:
                push(right)
                cur[prv_d] = cur = right
                right = right[0]
                prv_d = 0
        rest = left or right
        cur[prv_d] = rest
        if not prt:
            self.root = top[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

    # pop the k-th key
    def pop(self, k):
        # when pop(x), the tree should contain the k-th element
        rand = random.random
        node = self.root
        prt = None
        k += 1
        while 1:
            l = node[0]
            v = (l[3]+1 if l else 1)
            if v == k:
                break
            prt = node
            node[3] -= 1
            if k < v:
                node = node[0]
            else:
                k -= v
                node = node[1]
        r_node = node

        cur = top = prt
        if prt:
            prv_d = (prt[1] == node)
        else:
            cur = top = [None]
            prv_d = 0
        left, right = node[:2]
        st = []; push = st.append
        while left and right:
            a = left[3]; b = right[3]
            if int(rand() * (a+b)) < a:
                push(left)
                cur[prv_d] = cur = left
                left = left[1]
                prv_d = 1
            else:
                push(right)
                cur[prv_d] = cur = right
                right = right[0]
                prv_d = 0
        rest = left or right
        cur[prv_d] = rest
        if not prt:
            self.root = top[0]

        st.reverse()
        for node in st:
            l, r = node[:2]
            node[3] = (l[3] if l else 0) + (r[3] if r else 0) + 1

        return r_node[2]


Q,K = map(int,input().split())
rbst = RBST()
for q in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        v = query[1]
        rbst.insert(v)
    else:
        if len(rbst) >= K:
            print(rbst.pop(K-1))
        else:
            print(-1)
0