結果
| 問題 | No.1439 Let's Compare!!!! |
| ユーザー |
 titan23
|
| 提出日時 | 2022-10-05 00:13:59 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 621 ms / 2,000 ms |
| コード長 | 10,464 bytes |
| コンパイル時間 | 443 ms |
| コンパイル使用メモリ | 82,248 KB |
| 実行使用メモリ | 106,784 KB |
| 最終ジャッジ日時 | 2024-06-09 18:23:45 |
| 合計ジャッジ時間 | 7,438 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 37 ms
54,964 KB |
| testcase_01 | AC | 36 ms
55,228 KB |
| testcase_02 | AC | 37 ms
54,808 KB |
| testcase_03 | AC | 36 ms
55,616 KB |
| testcase_04 | AC | 38 ms
55,992 KB |
| testcase_05 | AC | 38 ms
54,680 KB |
| testcase_06 | AC | 37 ms
55,108 KB |
| testcase_07 | AC | 134 ms
78,532 KB |
| testcase_08 | AC | 151 ms
79,184 KB |
| testcase_09 | AC | 117 ms
77,336 KB |
| testcase_10 | AC | 616 ms
105,812 KB |
| testcase_11 | AC | 621 ms
97,392 KB |
| testcase_12 | AC | 568 ms
97,340 KB |
| testcase_13 | AC | 610 ms
106,784 KB |
| testcase_14 | AC | 615 ms
106,372 KB |
| testcase_15 | AC | 534 ms
97,348 KB |
| testcase_16 | AC | 434 ms
97,492 KB |
| testcase_17 | AC | 489 ms
97,656 KB |
| testcase_18 | AC | 150 ms
97,524 KB |
ソースコード
import sys
input = lambda: sys.stdin.readline().rstrip()
class AVLNodeSet:
__slots__ = ('key', 'size', 'left', 'right', 'balance')
def __init__(self, key):
self.key = key
self.size = 1
self.left = None
self.right = None
self.balance = 0
class AVLTreeSet:
__slots__ = ('node', '__iter')
__LEFT, __RIGHT = 1, -1
def __init__(self, V=[]) -> None:
# Make a new AVLTree.
# V: Iterable
self.node = None
self.__build(V)
def __build(self, V) -> None:
for v in sorted(V):
self.add(v)
def __rotate_L(self, node: AVLNodeSet) -> AVLNodeSet:
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, node.balance = 0, 0
else:
u.balance, node.balance = -1, 1
return u
def __rotate_R(self, node: AVLNodeSet) -> AVLNodeSet:
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, node.balance = 0, 0
else:
u.balance, node.balance = 1, -1
return u
def __update_balance(self, node: AVLNodeSet) -> None:
# nodeはnew_node
if node.balance == 1:
node.right.balance, node.left.balance = -1, 0
elif node.balance == -1:
node.right.balance, node.left.balance = 0, 1
else:
node.right.balance, node.left.balance = 0, 0
node.balance = 0
def __rotate_LR(self, node: AVLNodeSet) -> AVLNodeSet:
# 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: AVLNodeSet) -> AVLNodeSet:
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 add(self, key) -> bool:
'''add key. / O(logN)'''
if self.node is None:
self.node = AVLNodeSet(key)
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:
return False
pnode, di = path[-1]
if di == self.__LEFT:
pnode.left = AVLNodeSet(key)
else:
pnode.right = AVLNodeSet(key)
while path:
new_node = None
pnode, di = path.pop()
pnode.size += 1
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
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 True
def remove(self, key) -> bool:
'''Remove key. / O(logN)'''
if self.discard(key):
return True
raise KeyError(f'{key} is not exist.')
def discard(self, key) -> bool:
'''Discard key. / O(logN)'''
path = []
node = self.node
while node is not None:
if key < node.key:
path.append((node, self.__LEFT))
node = node.left
elif key > node.key:
path.append((node, self.__RIGHT))
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))
lmax = node.left
while lmax.right is not None:
path.append((lmax, self.__RIGHT))
lmax = lmax.right
node.key = lmax.key
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 = path.pop()
pnode.balance -= di
pnode.size -= 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 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 count(self, key) -> int:
'''Return the number of key. / O(logN)'''
return 1 if key in self else 0
def le(self, key):
'''Find the largest element <= key, or None if it doesn't exist. / O(logN)'''
res = None
node = self.node
while node is not None:
if key < node.key:
node = node.left
elif key > node.key:
res = node.key
node = node.right
else:
res = node.key
break
return res
def lt(self, key):
'''Find the largest element < key, or None if it doesn't exist. / O(logN)'''
res = None
node = self.node
while node is not None:
if key < node.key:
node = node.left
elif key > node.key:
res = node.key
node = node.right
else:
break
return res
def ge(self, key):
'''Find the smallest element >= key, or None if it doesn't exist. / O(logN)'''
res = None
node = self.node
while node is not None:
if key < node.key:
res = node.key
node = node.left
elif key > node.key:
node = node.right
else:
res = node.key
break
return res
def gt(self, key):
'''Find the smallest element > key, or None if it doesn't exist. / O(logN)'''
res = None
node = self.node
while node is not None:
if key < node.key:
res = node.key
node = node.left
elif key > node.key:
node = node.right
else:
break
return res
def index(self, key) -> int:
'''Count the number of elements < key. / O(logN)'''
indx = 0
node = self.node
while node:
if key < node.key:
node = node.left
elif key > node.key:
indx += 1 if node.left is None else node.left.size + 1
node = node.right
else:
indx += 0 if node.left is None else node.left.size
break
return indx
def index_right(self, key) -> int:
'''Count the number of elements <= key. / O(logN)'''
indx = 0
node = self.node
while node:
if key < node.key:
node = node.left
elif key > node.key:
indx += 1 if node.left is None else node.left.size + 1
node = node.right
else:
indx += 1 if node.left is None else node.left.size + 1
break
return indx
def pop(self, p=-1):
'''Return and Remove max element or a[p]. / O(logN)'''
if p < 0:
p += self.__len__()
x = self.__kth_elm(p)
self.discard(x)
return x
def popleft(self):
'''Return and Remove min element. / O(logN)'''
return self.pop(0)
def __kth_elm(self, k):
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
raise IndexError(f'k={k}, len={self.__len__()}')
def __contains__(self, x):
node = self.node
while node:
if x < node.key:
node = node.left
elif x > node.key:
node = node.right
else:
return True
return False
def __getitem__(self, x):
return self.__kth_elm(x)
def __iter__(self):
self.__iter = 0
return self
def __next__(self):
if self.__iter == self.__len__():
raise StopIteration
res = self.__getitem__(self.__iter)
self.__iter += 1
return res
def __reversed__(self):
for i in range(self.__len__()):
yield self.__getitem__(-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(str, self)) + '}'
def __str__(self):
return '{' + ', '.join(map(str, self)) + '}'
# ----------------------- #
n = int(input())
S = list(map(int, input()))
T = list(map(int, input()))
comp = [i for i in range(n) if S[i] != T[i]]
avl = AVLTreeSet(comp)
q = int(input())
for _ in range(q):
c, x, y = input().split()
x, y = int(x), int(y)
x -= 1
if c == 'S':
S[x] = y
else:
T[x] = y
if S[x] != T[x]:
avl.add(x)
else:
avl.discard(x)
if avl:
keta = avl[0]
if S[keta] < T[keta]:
print('<')
else:
print('>')
else:
print('=')