結果

問題 No.1439 Let's Compare!!!!
ユーザー titan23
提出日時 2022-10-05 00:13:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 789 ms / 2,000 ms
コード長 10,464 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 106,740 KB
最終ジャッジ日時 2024-12-30 15:31:51
合計ジャッジ時間 8,652 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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('=')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0