結果
| 問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
| ユーザー |
 titan23
|
| 提出日時 | 2022-09-29 21:44:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 22,195 bytes |
| コンパイル時間 | 481 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 106,568 KB |
| 最終ジャッジ日時 | 2024-12-22 18:27:54 |
| 合計ジャッジ時間 | 35,654 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 WA * 35 |
ソースコード
import sys
input = lambda: sys.stdin.readline().rstrip()
class AVLNode:
__slots__ = ('key', 'val', 'size', 'left', 'right', 'balance')
def __init__(self, key, val):
self.key = key
self.val = val
self.size = 1
self.left = None
self.right = None
self.balance = 0
class AVLTreeDict:
__slots__ = ('node', '__iter', '__default')
__LEFT, __RIGHT = 1, -1
def __init__(self, V=[], c=False, default=None) -> None:
self.__default = default
self.node = None
if c:
self.__default = int
self.__build(V)
def __build(self, V) -> None:
for v in sorted(V):
self.__setitem__(v, self.__getitem__(v)+1)
def __rotate_L(self, node: AVLNode) -> AVLNode:
u = node.left
u.size = node.size
node.size -= 1 if u.left is None else u.left.size + 1
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
node.size -= 1 if u.right is None else u.right.size + 1
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
B = node.left
E = B.right
E.size = node.size
ers = 0 if E.right is None else E.right.size
node.size -= B.size - ers
B.size -= ers + 1
B.right = E.left
E.left = B
node.left = E.right
E.right = node
self.__update_balance(E)
return E
def __rotate_RL(self, node: AVLNode) -> AVLNode:
C = node.right
D = C.left
D.size = node.size
dls = 0 if D.left is None else D.left.size
node.size -= C.size - dls
C.size -= dls + 1
C.left = D.right
D.right = C
node.right = D.left
D.left = node
self.__update_balance(D)
return D
def __kth_elm(self, k: int) -> tuple:
if k < 0:
k += self.__len__()
now = 0
node = self.node
while node is not None:
t = now if node.left is None else now + node.left.size
if t < k:
now = t + 1
node = node.right
elif t > k:
node = node.left
else:
return node.key, node.val
raise IndexError(f'k={k}, len={self.__len__()}')
def items(self) -> tuple:
indx = 0
while indx < self.__len__():
yield self.__kth_elm(indx)
indx += 1
def keys(self):
indx = 0
while indx < self.__len__():
yield self.__kth_elm(indx)[0]
indx += 1
def values(self):
indx = 0
while indx < self.__len__():
yield self.__kth_elm(indx)[1]
indx += 1
def __search_node(self, key) -> AVLNode:
node = self.node
while node:
if key < node.key:
node = node.left
elif key > node.key:
node = node.right
else:
break
return node
def __discard(self, key) -> bool:
'''Discard a key. / 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
else:
return False
if node.left is not None and node.right 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
if pnode.balance > 1:
if pnode.left.balance < 0:
new_node = self.__rotate_LR(pnode)
else:
new_node = self.__rotate_L(pnode)
elif pnode.balance < -1:
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 not path:
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:
path.pop()[0].size -= 1
return True
def __setitem__(self, key, val):
'''add a key. / O(logN)'''
if self.node is None:
self.node = AVLNode(key, val)
return True
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 = val
return
pnode, di = path[-1]
if di == self.__LEFT:
pnode.left = AVLNode(key, val)
else:
pnode.right = AVLNode(key, val)
while path:
new_node = None
pnode, di = path.pop()
pnode.size += 1
pnode.balance += di
if pnode.balance == 0:
break
if pnode.balance > 1: # pnodeの左部分木が茂りすぎ
if pnode.left.balance < 0:
# LR2重回転: nodeの右側が茂っている場合
new_node = self.__rotate_LR(pnode)
else:
# LL1重回転: nodeの左側が茂っている場合
new_node = self.__rotate_L(pnode)
break
elif pnode.balance < -1: # pnodeの右部分木が茂りすぎ
if pnode.right.balance > 0:
# 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
if gdi == self.__LEFT:
gnode.left = new_node
else:
gnode.right = new_node
else:
self.node = new_node
return
while path:
path.pop()[0].size += 1
return
def __delitem__(self, key):
'''Remove a key. / O(logN)'''
if self.__discard(key):
return
raise KeyError(key)
def __getitem__(self, key):
node = self.__search_node(key)
return self.__missing__() if node is None else node.val
def __contains__(self, key):
return self.__search_node(key) is not None
def __reversed__(self):
for i in range(self.__len__()):
yield self.__kth_elm(-i-1)
def __len__(self):
return 0 if self.node is None else self.node.size
def __bool__(self):
return self.node is not None
def __repr__(self):
return '{' + ', '.join(map(lambda x: f'{x[0]}: {x[1]}', self.items())) + '}'
def __str__(self):
return '{' + ', '.join(map(lambda x: f'{x[0]}: {x[1]}', self.items())) + '}'
def __missing__(self):
return self.__default()
def __iter__(self):
self.__iter = 0
return self
def __next__(self):
if self.__iter == self.__len__():
raise StopIteration
res = self.__kth_elm(self.__iter)[0]
self.__iter += 1
return res
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()
# ----------------------- #
n = int(input())
L = list(map(int, input().split()))
for i in range(len(L)):
L[i] *= 10**9
cnt = [0] * len(L)
score_dict = AVLTreeDict(default=int)
score_set = AVLTreeMultiSet()
alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
t = int(input())
for i in range(t):
name, p = input().split()
if p == '?':
print(len(score_dict)-score_set.index(score_dict[name]))
else:
q = alp.index(p)
cnt[q] += 1
star = L[q]
prescore = score_dict[name]
newscore = prescore + star*50 + int(star*50/(0.8 + 0.2*cnt[q])) - i
score_dict[name] = newscore
score_set.discard(prescore)
score_set.add(newscore)