結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 titan23
|
| 提出日時 | 2022-09-29 21:16:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 776 ms / 3,000 ms |
| コード長 | 13,662 bytes |
| コンパイル時間 | 271 ms |
| コンパイル使用メモリ | 87,156 KB |
| 実行使用メモリ | 120,908 KB |
| 最終ジャッジ日時 | 2023-08-24 05:03:13 |
| 合計ジャッジ時間 | 15,175 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 74 ms
71,316 KB |
| testcase_01 | AC | 71 ms
71,316 KB |
| testcase_02 | AC | 71 ms
71,396 KB |
| testcase_03 | AC | 188 ms
98,292 KB |
| testcase_04 | AC | 355 ms
120,560 KB |
| testcase_05 | AC | 340 ms
120,568 KB |
| testcase_06 | AC | 214 ms
96,828 KB |
| testcase_07 | AC | 72 ms
71,408 KB |
| testcase_08 | AC | 70 ms
71,320 KB |
| testcase_09 | AC | 71 ms
71,404 KB |
| testcase_10 | AC | 71 ms
71,276 KB |
| testcase_11 | AC | 71 ms
71,396 KB |
| testcase_12 | AC | 432 ms
98,600 KB |
| testcase_13 | AC | 452 ms
99,392 KB |
| testcase_14 | AC | 434 ms
98,704 KB |
| testcase_15 | AC | 516 ms
101,328 KB |
| testcase_16 | AC | 419 ms
99,700 KB |
| testcase_17 | AC | 448 ms
101,084 KB |
| testcase_18 | AC | 519 ms
104,372 KB |
| testcase_19 | AC | 547 ms
106,392 KB |
| testcase_20 | AC | 561 ms
108,496 KB |
| testcase_21 | AC | 634 ms
111,152 KB |
| testcase_22 | AC | 625 ms
112,392 KB |
| testcase_23 | AC | 631 ms
114,444 KB |
| testcase_24 | AC | 698 ms
116,752 KB |
| testcase_25 | AC | 755 ms
118,276 KB |
| testcase_26 | AC | 776 ms
120,908 KB |
| testcase_27 | AC | 104 ms
77,864 KB |
| testcase_28 | AC | 102 ms
76,488 KB |
| testcase_29 | AC | 100 ms
76,512 KB |
| testcase_30 | AC | 421 ms
97,092 KB |
| testcase_31 | AC | 402 ms
96,744 KB |
| testcase_32 | AC | 72 ms
71,312 KB |
| testcase_33 | AC | 71 ms
71,672 KB |
| testcase_34 | AC | 71 ms
71,552 KB |
| testcase_35 | AC | 71 ms
71,320 KB |
ソースコード
import sys
input = lambda: sys.stdin.readline().rstrip()
class AVLNode:
__slots__ = ('key', 'val', 'size', 'valsize', 'left', 'right', 'balance')
def __init__(self, key, val):
self.key = key
self.val = val
self.valsize = val
self.size = 1
self.left = None
self.right = None
self.balance = 0
def __str__(self):
if self.left is None and self.right is None:
return f'key:{self.key, self.val, self.valsize, self.size}\n'
return f'key:{self.key, self.val, self.valsize, self.size},\n left:{self.left},\n right:{self.right}\n'
class AVLTreeMultiSet:
__slots__ = ('node', '__iter')
__LEFT, __RIGHT = 1, -1
def __init__(self, V=[]):
self.node = None
self.__build(V)
def __build(self, V):
for v in sorted(V):
self.add(v, 1)
def __rotate_L(self, node: AVLNode) -> AVLNode:
u = node.left
u.size = node.size
u.valsize = node.valsize
node.size -= 1 if u.left is None else u.left.size + 1
node.valsize -= u.val if u.left is None else u.left.valsize + u.val
node.left = u.right
u.right = node
if u.balance == 1:
u.balance = 0
node.balance = 0
else:
u.balance = -1
node.balance = 1
return u
def __rotate_R(self, node: AVLNode) -> AVLNode:
u = node.right
u.size = node.size
u.valsize = node.valsize
node.size -= 1 if u.right is None else u.right.size + 1
node.valsize -= u.val if u.right is None else u.right.valsize + u.val
node.right = u.left
u.left = node
if u.balance == -1:
u.balance = 0
node.balance = 0
else:
u.balance = 1
node.balance = -1
return u
def __update_balance(self, node: AVLNode) -> None:
# nodeはnew_node
if node.balance == 1:
node.right.balance = -1
node.left.balance = 0
elif node.balance == -1:
node.right.balance = 0
node.left.balance = 1
else:
node.right.balance = 0
node.left.balance = 0
node.balance = 0
def __rotate_LR(self, node: AVLNode) -> AVLNode:
# A E
# / \ / \
# B C -> B A
# /\ /\ /\
# D E D F1F2 C
# /\
# F1 F2
# # node: A
E = node.left.right
F1 = E.left
F2 = E.right
E.left = node.left
E.left.right = F1
E.right = node
E.right.left = F2
E.left.size = 1 + (0 if E.left.right is None else E.left.right.size) + (0 if E.left.left is None else E.left.left.size)
E.right.size = 1 + (0 if E.right.right is None else E.right.right.size) + (0 if E.right.left is None else E.right.left.size)
E.size = E.left.size + E.right.size + 1
E.left.valsize = E.left.val + (0 if E.left.right is None else E.left.right.valsize) + (0 if E.left.left is None else E.left.left.valsize)
E.right.valsize = E.right.val + (0 if E.right.right is None else E.right.right.valsize) + (0 if E.right.left is None else E.right.left.valsize)
E.valsize = E.left.valsize + E.right.valsize + E.val
self.__update_balance(E)
return E
def __rotate_RL(self, node: AVLNode) -> AVLNode:
D = node.right.left
F1 = D.left
F2 = D.right
D.right = node.right
D.right.left = F2
D.left = node
D.left.right = F1
D.right.size = 1 + (0 if D.right.left is None else D.right.left.size) + (0 if D.right.right is None else D.right.right.size)
D.left.size = 1 + (0 if D.left.left is None else D.left.left.size) + (0 if D.left.right is None else D.left.right.size)
D.size = D.right.size + D.left.size + 1
D.right.valsize = D.right.val + (0 if D.right.left is None else D.right.left.valsize) + (0 if D.right.right is None else D.right.right.valsize)
D.left.valsize = D.left.val + (0 if D.left.left is None else D.left.left.valsize) + (0 if D.left.right is None else D.left.right.valsize)
D.valsize = D.right.valsize + D.left.valsize + D.val
self.__update_balance(D)
return D
def __discard(self, key) -> bool:
'''Discard node of key from self. / O(logN)'''
path = []
node = self.node
while node is not None:
if key < node.key:
path.append((node, self.__LEFT, 0))
node = node.left
elif key > node.key:
path.append((node, self.__RIGHT, 0))
node = node.right
else:
break
if node.left is not None:
path.append((node, self.__LEFT, 0))
lmax = node.left
while lmax.right is not None:
path.append((lmax, self.__RIGHT, 1))
lmax = lmax.right
node.key = lmax.key
node.val = lmax.val
lmax_val = lmax.val
node = lmax
cnode = node.right if node.left is None else node.left
if path:
pnode, di, _ = path[-1]
if di == self.__LEFT:
pnode.left = cnode
else:
pnode.right = cnode
else:
self.node = cnode
return True
while path:
new_node = None
pnode, di, flag = path.pop()
pnode.balance -= di
pnode.size -= 1
pnode.valsize -= lmax_val if flag else 1
if pnode.balance == 2:
if pnode.left.balance < 0:
new_node = self.__rotate_LR(pnode)
else:
new_node = self.__rotate_L(pnode)
elif pnode.balance == -2:
if pnode.right.balance > 0:
new_node = self.__rotate_RL(pnode)
else:
new_node = self.__rotate_R(pnode)
elif pnode.balance != 0:
break
if new_node is not None:
if len(path) == 0:
self.node = new_node
return
gnode, gdir, _ = path[-1]
if gdir == self.__LEFT:
gnode.left = new_node
else:
gnode.right = new_node
if new_node.balance != 0:
break
while path:
pnode, _, flag = path.pop()
pnode.size -= 1
pnode.valsize -= lmax_val if flag else 1
return True
def discard(self, key, cnt=1) -> bool:
path = []
node = self.node
while node is not None:
if key < node.key:
path.append(node)
node = node.left
elif key > node.key:
path.append(node)
node = node.right
else:
path.append(node)
break
else:
return False
if cnt >= node.val:
cnt = node.val - 1
path[-1].val -= cnt
while path:
pnode = path.pop()
pnode.valsize -= cnt
if node.val == 1:
self.__discard(key)
else:
path[-1].val -= cnt
while path:
pnode = path.pop()
pnode.valsize -= cnt
return True
def __getval(self, key):
node = self.node
while node:
if node.key == key:
return node.val
elif key < node.key:
node = node.left
else:
node = node.right
raise KeyError
def add(self, key, cnt=1) -> None:
'''add key cnt times. / O(logN)'''
if self.node is None:
self.node = AVLNode(key, cnt)
return
pnode = self.node
path = []
while pnode is not None:
if key < pnode.key:
path.append((pnode, self.__LEFT))
pnode = pnode.left
elif key > pnode.key:
path.append((pnode, self.__RIGHT))
pnode = pnode.right
else:
pnode.val += cnt
pnode.valsize += cnt
while path:
pnode, _ = path.pop()
pnode.valsize += cnt
return
pnode, di = path[-1]
if di == self.__LEFT:
pnode.left = AVLNode(key, cnt)
else:
pnode.right = AVLNode(key, cnt)
while path:
new_node = None
pnode, di = path.pop()
pnode.size += 1
pnode.valsize += cnt
pnode.balance += di
if pnode.balance == 0:
break
if pnode.balance == 2: # pnodeの左部分木が茂りすぎ
if pnode.left.balance == -1:
# LR2重回転: nodeの右側が茂っている場合
new_node = self.__rotate_LR(pnode)
else:
# LL1重回転: nodeの左側が茂っている場合
new_node = self.__rotate_L(pnode)
break
elif pnode.balance == -2: # pnodeの右部分木が茂りすぎ
if pnode.right.balance == 1:
# RL2重回転: nodeの左側が茂っている場合
new_node = self.__rotate_RL(pnode)
else:
# RR1重回転: nodeの右側が茂っている場合
new_node = self.__rotate_R(pnode)
break
# else: 最初にpnode.balanceを更新したので、何もせずcontinueしてOK
if new_node is not None:
if path:
gnode, gdi = path.pop()
gnode.size += 1
gnode.valsize += cnt
if gdi == self.__LEFT:
gnode.left = new_node
else:
gnode.right = new_node
else:
self.node = new_node
while path:
pnode, _ = path.pop()
pnode.size += 1
pnode.valsize += cnt
return
def count(self, key) -> int:
pass
return self.__getval(key)
def le(self, key):
'''Find the largest element <= key, or None if it doesn't exist. / O(logN)'''
if key in self:
return key
indx = self.index(key)
return self.__getitem__(indx-1) if 0 <= indx-1 < self.__len__() else None
def lt(self, key):
'''Find the largest element < key, or None if it doesn't exist. / O(logN)'''
indx = self.index(key)
return self.__getitem__(indx-1) if 0 <= indx-1 < self.__len__() else None
def ge(self, key):
'''Find the smallest element >= key, or None if it doesn't exist. / O(logN)'''
if key in self:
return key
indx = self.index_right(key)
return self.__getitem__(indx) if 0 <= indx < self.__len__() else None
def gt(self, key):
'''Find the smallest element > key, or None if it doesn't exist. / O(logN)'''
indx = self.index_right(key)
return self.__getitem__(indx) if 0 <= indx < self.__len__() else None
def index(self, key) -> int:
'''Count the number of elements < key. / O(logN)'''
indx = 0
node = self.node
while node:
if node.key == key:
indx += 0 if node.left is None else node.left.valsize
break
elif key < node.key:
node = node.left
else:
indx += node.val if node.left is None else node.left.valsize + node.val
node = node.right
return indx
def index_right(self, key) -> int:
'''Count the number of elements <= key. / O(logN)'''
indx = 0
node = self.node
while node:
if node.key == key:
indx += (0 if node.left is None else node.left.valsize) + node.val
break
elif key < node.key:
node = node.left
else:
indx += (0 if node.left is None else node.left.valsize) + node.val
node = node.right
return indx
def pop(self, p=-1):
'''Return and Remove max element or a[p]. / O(logN)'''
if p < 0:
p += self.__len__()
assert 0 <= p < self.__len__()
x = self.__getitem__(p)
self.discard(x)
return x
def popleft(self):
'''Return and Remove min element. / O(logN)'''
return self.pop(0)
def items(self):
indx = 0
while indx < self.__len_tree():
yield self.__kth_elm_tree(indx)
indx += 1
def keys(self):
indx = 0
while indx < self.__len_tree():
yield self.__kth_elm_tree(indx)[0]
indx += 1
def values(self):
indx = 0
while indx < self.__len_tree():
yield self.__kth_elm_tree(indx)[1]
indx += 1
def __getitem__(self, k):
return self.__kth_elm_set(k)[0]
def __kth_elm_set(self, k) -> tuple:
if k < 0:
k += self.__len__()
now = 0
node = self.node
while node is not None:
s = now + node.left.valsize if node.left is not None else now
t = s + node.val
if s <= k < t:
return node.key, node.val
elif t <= k:
now = t
node = node.right
else:
node = node.left
raise IndexError
def __kth_elm_tree(self, k) -> tuple:
if k < 0:
k += self.__len_tree()
now = 0
node = self.node
while node is not None:
t = now + node.left.size if node.left is not None else now
if t == k:
return node.key, node.val
elif t < k:
now = t + 1
node = node.right
else:
node = node.left
raise IndexError
def __contains__(self, key):
node = self.node
while node:
if node.key == key:
return True
elif key < node.key:
node = node.left
else:
node = node.right
return False
def __iter__(self):
self.__iter = 0
return self
def __next__(self):
if self.__iter == self.__len__():
raise StopIteration
res = self.__kth_elm_set(self.__iter)
self.__iter += 1
return res
def __reversed__(self):
for i in range(self.__len__()):
yield self.__kth_elm_set(-i-1)
def __len_tree(self):
return 0 if self.node is None else self.node.size
def __len__(self):
return 0 if self.node is None else self.node.valsize
def __bool__(self):
return True if self.node is not None else False
def __str__(self):
return '{' + ', '.join(map(lambda x: ', '.join([str(x[0])]*x[1]), self.items())) + '}'
def show(self):
return '{' + ', '.join(map(lambda x: f'{x[0]}: {x[1]}', self.items())) + '}'
def __str__(self):
return '{' + ', '.join(map(lambda x: ', '.join([str(x[0])]*x[1]), self.items())) + '}'
def count_elm(self):
return self.__len_tree()
# ----------------------- #
q, k = map(int, input().split())
avl = AVLTreeMultiSet()
query = [list(map(int, input().split())) for _ in range(q)]
for qu in query:
if qu[0] == 1:
avl.add(qu[1])
else:
if len(avl) < k:
print(-1)
else:
print(avl.pop(k-1))