結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 Fuyuru
|
| 提出日時 | 2024-01-23 13:26:17 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,058 ms / 3,000 ms |
| コード長 | 4,882 bytes |
| コンパイル時間 | 373 ms |
| コンパイル使用メモリ | 81,572 KB |
| 実行使用メモリ | 111,392 KB |
| 最終ジャッジ日時 | 2024-01-23 13:26:36 |
| 合計ジャッジ時間 | 17,543 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 43 ms
56,136 KB |
| testcase_01 | AC | 42 ms
56,136 KB |
| testcase_02 | AC | 44 ms
56,136 KB |
| testcase_03 | AC | 125 ms
76,796 KB |
| testcase_04 | AC | 352 ms
101,844 KB |
| testcase_05 | AC | 346 ms
101,976 KB |
| testcase_06 | AC | 381 ms
98,252 KB |
| testcase_07 | AC | 42 ms
56,136 KB |
| testcase_08 | AC | 43 ms
56,136 KB |
| testcase_09 | AC | 43 ms
56,136 KB |
| testcase_10 | AC | 44 ms
56,136 KB |
| testcase_11 | AC | 43 ms
56,136 KB |
| testcase_12 | AC | 490 ms
90,720 KB |
| testcase_13 | AC | 521 ms
90,816 KB |
| testcase_14 | AC | 464 ms
90,676 KB |
| testcase_15 | AC | 560 ms
91,936 KB |
| testcase_16 | AC | 467 ms
91,944 KB |
| testcase_17 | AC | 627 ms
94,376 KB |
| testcase_18 | AC | 620 ms
95,936 KB |
| testcase_19 | AC | 681 ms
97,700 KB |
| testcase_20 | AC | 728 ms
99,536 KB |
| testcase_21 | AC | 787 ms
101,028 KB |
| testcase_22 | AC | 826 ms
103,008 KB |
| testcase_23 | AC | 882 ms
104,296 KB |
| testcase_24 | AC | 943 ms
106,636 KB |
| testcase_25 | AC | 986 ms
108,060 KB |
| testcase_26 | AC | 1,058 ms
111,392 KB |
| testcase_27 | AC | 74 ms
71,048 KB |
| testcase_28 | AC | 75 ms
71,040 KB |
| testcase_29 | AC | 73 ms
71,044 KB |
| testcase_30 | AC | 466 ms
91,812 KB |
| testcase_31 | AC | 504 ms
91,800 KB |
| testcase_32 | AC | 42 ms
56,136 KB |
| testcase_33 | AC | 43 ms
56,136 KB |
| testcase_34 | AC | 44 ms
56,136 KB |
| testcase_35 | AC | 42 ms
56,136 KB |
ソースコード
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)