結果

問題 No.2240 WAC
ユーザー titan23titan23
提出日時 2023-03-11 12:26:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 888 ms / 2,000 ms
コード長 9,308 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 130,544 KB
最終ジャッジ日時 2024-09-18 06:17:38
合計ジャッジ時間 19,053 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
68,864 KB
testcase_01 AC 67 ms
68,992 KB
testcase_02 AC 67 ms
68,864 KB
testcase_03 AC 68 ms
68,992 KB
testcase_04 AC 72 ms
69,544 KB
testcase_05 AC 68 ms
68,864 KB
testcase_06 AC 68 ms
69,120 KB
testcase_07 AC 68 ms
69,248 KB
testcase_08 AC 67 ms
69,504 KB
testcase_09 AC 68 ms
68,864 KB
testcase_10 AC 888 ms
113,936 KB
testcase_11 AC 870 ms
125,688 KB
testcase_12 AC 770 ms
130,544 KB
testcase_13 AC 385 ms
96,868 KB
testcase_14 AC 312 ms
86,916 KB
testcase_15 AC 454 ms
111,176 KB
testcase_16 AC 744 ms
116,720 KB
testcase_17 AC 714 ms
105,908 KB
testcase_18 AC 343 ms
89,756 KB
testcase_19 AC 378 ms
91,708 KB
testcase_20 AC 480 ms
116,644 KB
testcase_21 AC 481 ms
97,568 KB
testcase_22 AC 338 ms
97,096 KB
testcase_23 AC 381 ms
93,808 KB
testcase_24 AC 613 ms
113,324 KB
testcase_25 AC 804 ms
113,540 KB
testcase_26 AC 375 ms
91,176 KB
testcase_27 AC 334 ms
88,620 KB
testcase_28 AC 272 ms
93,828 KB
testcase_29 AC 184 ms
83,328 KB
testcase_30 AC 458 ms
101,068 KB
testcase_31 AC 811 ms
121,368 KB
testcase_32 AC 321 ms
88,448 KB
testcase_33 AC 666 ms
102,156 KB
testcase_34 AC 770 ms
106,020 KB
testcase_35 AC 232 ms
83,860 KB
testcase_36 AC 670 ms
112,024 KB
testcase_37 AC 498 ms
118,856 KB
testcase_38 AC 272 ms
93,808 KB
testcase_39 AC 568 ms
123,208 KB
testcase_40 AC 635 ms
102,128 KB
testcase_41 AC 414 ms
107,580 KB
testcase_42 AC 428 ms
105,924 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()

from typing import Optional, List, Iterable
from array import array

class BinaryTrieSet():

  def __init__(self, u: int, a: Iterable[int]=[]):
    self.left = array('I', bytes(8))
    self.right = array('I', bytes(8))
    self.par = array('I', bytes(8))
    self.size = array('I', bytes(8))
    self.end = 2
    self.root = 1
    self.bit = (u - 1).bit_length()
    self.lim = 1 << self.bit
    self.xor = 0
    for e in a:
      self.add(e)

  def _make_node(self) -> int:
    end = self.end
    if end >= len(self.left):
      self.left.append(0)
      self.right.append(0)
      self.par.append(0)
      self.size.append(0)
    self.end += 1
    return end

  def reserve(self, n: int) -> None:
    assert n >= 0, f'ValueError: BinaryTrieSet.reserve({n})'
    a = array('I', bytes(4*n))
    self.left += a
    self.right += a
    self.par += a
    self.size += a

  def add(self, key: int) -> bool:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.add({key}), lim={self.lim}'
    left, right, par, size = self.left, self.right, self.par, self.size
    key ^= self.xor
    node = self.root
    for i in range(self.bit-1, -1, -1):
      if key >> i & 1:
        left, right = right, left
      if not left[node]:
        left[node] = self._make_node()
        par[left[node]] = node
      node = left[node]
      if key >> i & 1:
        left, right = right, left
    if size[node]: return False
    size[node] = 1
    for i in range(self.bit):
      node = par[node]
      size[node] += 1
    return True

  def _discard(self, node: int) -> None:
    left, right, par, size = self.left, self.right, self.par, self.size
    for i in range(self.bit):
      size[node] -= 1
      if left[par[node]] == node:
        node = par[node]
        left[node] = 0
        if right[node]: break
      else:
        node = par[node]
        right[node] = 0
        if left[node]: break
    while node:
      size[node] -= 1
      node = par[node]

  def discard(self, key: int) -> bool:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.discard({key}), lim={self.lim}'
    left, right, par, size = self.left, self.right, self.par, self.size
    node = self.find(key)
    if not node: return False
    self._discard(node)
    return True

  def pop(self, k: int=-1) -> int:
    assert -len(self) <= k < len(self), \
        f'IndexError: BinaryTrieSet.pop({k}), len={len(self)}'
    left, right, size = self.left, self.right, self.size
    node = self.root
    res = 0
    for i in range(self.bit-1, -1, -1):
      b = self.xor >> i & 1
      if b:
        left, right = right, left
      t = size[left[node]]
      res <<= 1
      if not left[node]:
        node = right[node]
        res |= 1
      elif not right[node]:
        node = left[node]
      else:
        t = size[left[node]]
        if t <= k:
          k -= t
          res |= 1
          node = right[node]
        else:
          node = left[node]
      if b:
        left, right = right, left
    self._discard(node)
    return res ^ self.xor

  def pop_min(self) -> int:
    assert self, f'IndexError: BinaryTrieSet.pop_min(), len={len(self)}'
    return self.pop(0)

  def find(self, key: int) -> Optional[int]:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.find({key}), lim={self.lim}'
    left, right = self.left, self.right
    key ^= self.xor
    node = self.root
    for i in range(self.bit-1, -1, -1):
      if key >> i & 1:
        left, right = right, left
      if not left[node]: return None
      node = left[node]
      if key >> i & 1:
        left, right = right, left
    return node

  def all_xor(self, x: int) -> None:
    assert 0 <= x < self.lim, \
        f'ValueError: BinaryTrieSet.all_xor({x}), lim={self.lim}'
    self.xor ^= x

  def get_min(self) -> int:
    assert self, f'IndexError: BinaryTrieSet.get_min()'
    left, right = self.left, self.right
    key = self.xor
    ans = 0
    node = self.root
    for i in range(self.bit-1, -1, -1):
      ans <<= 1
      if key >> i & 1:
        if right[node]:
          node = right[node]
          ans |= 1
        else:
          node = left[node]
      else:
        if left[node]:
          node = left[node]
        else:
          node = right[node]
          ans |= 1
    return ans ^ self.xor

  def get_max(self) -> int:
    assert self, f'IndexError: BinaryTrieSet.get_max()'
    left, right = self.left, self.right
    key = self.xor
    ans = 0
    node = self.root
    for i in range(self.bit-1, -1, -1):
      ans <<= 1
      if key >> i & 1:
        if left[node]:
          node = left[node]
        else:
          node = right[node]
          ans |= 1
      else:
        if right[node]:
          ans |= 1
          node = right[node]
        else:
          node = left[node]
    return ans ^ self.xor

  def index(self, key: int) -> int:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.index({key}), lim={self.lim}'
    left, right, size = self.left, self.right, self.size
    k, now = 0, 0
    node = self.root
    key ^= self.xor
    for i in range(self.bit-1, -1, -1):
      if key >> i & 1:
        k += size[left[node]]
        node = right[node]
      else:
        node = left[node]
      if not node: break
    return k

  def index_right(self, key: int) -> int:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.index_right({key}), lim={self.lim}'
    left, right, size = self.left, self.right, self.size
    k, now = 0, 0
    node = self.root
    key ^= self.xor
    for i in range(self.bit-1, -1, -1):
      if key >> i & 1:
        k += size[left[node]]
        node = right[node]
      else:
        node = left[node]
      if not node: break
    else:
      k += 1
    return k

  def gt(self, key: int) -> Optional[int]:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.gt({key}), lim={self.lim}'
    i = self.index_right(key)
    return None if i >= self.size[self.root] else self.__getitem__(i)

  def lt(self, key: int) -> Optional[int]:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.lt({key}), lim={self.lim}'
    i = self.index(key) - 1
    return None if i < 0 else self.__getitem__(i)

  def ge(self, key: int) -> Optional[int]:
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.ge({key}), lim={self.lim}'
    if key == 0: return self.get_min() if self else None
    i = self.index_right(key - 1)
    return None if i >= self.size[self.root] else self.__getitem__(i)

  def le(self, key: int):
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.le({key}), lim={self.lim}'
    i = self.index(key + 1) - 1
    return None if i < 0 else self.__getitem__(i)

  def tolist(self) -> List[int]:
    a = []
    if not self: return a
    val = self.get_min()
    while val is not None:
      a.append(val)
      val = self.gt(val)
    return a

  def __contains__(self, key: int):
    assert 0 <= key < self.lim, \
        f'ValueError: BinaryTrieSet.__contains__({key}), lim={self.lim}'
    return self.find(key) is not None

  def __getitem__(self, k: int):
    assert -len(self) <= k < len(self), \
        f'IndexError: BinaryTrieSet.__getitem__({k}), len={len(self)}'
    if k < 0: k += len(self)
    left, right, size = self.left, self.right, self.size
    node = self.root
    res = 0
    for i in range(self.bit-1, -1, -1):
      b = self.xor >> i & 1
      if b:
        left, right = right, left
      t = size[left[node]]
      res <<= 1
      if not left[node]:
        node = right[node]
        res |= 1
      elif not right[node]:
        node = left[node]
      else:
        t = size[left[node]]
        if t <= k:
          k -= t
          res |= 1
          node = right[node]
        else:
          node = left[node]
      if b:
        left, right = right, left
    return res

  def __bool__(self):
    return self.size[self.root] != 0

  def __iter__(self):
    self.it = 0
    return self

  def __next__(self):
    if self.it == len(self):
      raise StopIteration
    self.it += 1
    return self.__getitem__(self.it-1)

  def __len__(self):
    return self.size[self.root]

  def __str__(self):
    return '{' + ', '.join(map(str, self)) + '}'

  def __repr__(self):
    return f'BinaryTrieSet({(1<<self.bit)-1}, {self})'

#  -----------------------  #

n, m = map(int, input().split())
s = input()
def solve1():
  W = BinaryTrieSet(len(s))
  A = BinaryTrieSet(len(s))
  C = BinaryTrieSet(len(s))
  for i, c in enumerate(s):
    if c == 'W':
      W.add(i)
    elif c == 'A':
      A.add(i)
    else:
      C.add(i)
  for _ in range(n):
    w = W.pop_min()
    a = A.pop()
    if w > a:
      return False
  for _ in range(m):
    a = A.pop()
    c = C.pop()
    if a > c:
      return False
  return True

def solve2():
  W = BinaryTrieSet(len(s))
  A = BinaryTrieSet(len(s))
  C = BinaryTrieSet(len(s))
  for i, c in enumerate(s):
    if c == 'W':
      W.add(i)
    elif c == 'A':
      A.add(i)
    else:
      C.add(i)
  for _ in range(m):
    a = A.pop_min()
    c = C.pop()
    if a > c:
      return False
  for _ in range(n):
    w = W.pop()
    a = A.pop()
    if w > a:
      return False
  return True

print('Yes' if solve1() or solve2() else 'No')
0