結果

問題 No.2240 WAC
ユーザー titan23titan23
提出日時 2023-03-11 12:35:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 873 ms / 2,000 ms
コード長 9,361 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 131,188 KB
最終ジャッジ日時 2024-09-18 06:17:58
合計ジャッジ時間 19,429 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
69,804 KB
testcase_01 AC 65 ms
69,940 KB
testcase_02 AC 65 ms
70,172 KB
testcase_03 AC 67 ms
69,756 KB
testcase_04 AC 64 ms
71,380 KB
testcase_05 AC 65 ms
70,168 KB
testcase_06 AC 65 ms
69,540 KB
testcase_07 AC 66 ms
71,432 KB
testcase_08 AC 65 ms
70,124 KB
testcase_09 AC 64 ms
70,780 KB
testcase_10 AC 864 ms
113,272 KB
testcase_11 AC 873 ms
125,440 KB
testcase_12 AC 762 ms
131,188 KB
testcase_13 AC 368 ms
96,216 KB
testcase_14 AC 304 ms
87,320 KB
testcase_15 AC 443 ms
112,256 KB
testcase_16 AC 735 ms
116,204 KB
testcase_17 AC 709 ms
105,912 KB
testcase_18 AC 352 ms
90,184 KB
testcase_19 AC 381 ms
91,528 KB
testcase_20 AC 466 ms
117,160 KB
testcase_21 AC 474 ms
98,152 KB
testcase_22 AC 325 ms
98,896 KB
testcase_23 AC 378 ms
94,200 KB
testcase_24 AC 594 ms
112,700 KB
testcase_25 AC 797 ms
110,716 KB
testcase_26 AC 393 ms
90,800 KB
testcase_27 AC 349 ms
89,352 KB
testcase_28 AC 272 ms
94,596 KB
testcase_29 AC 182 ms
83,964 KB
testcase_30 AC 460 ms
102,808 KB
testcase_31 AC 821 ms
119,576 KB
testcase_32 AC 329 ms
88,932 KB
testcase_33 AC 675 ms
101,900 KB
testcase_34 AC 780 ms
108,284 KB
testcase_35 AC 237 ms
83,556 KB
testcase_36 AC 678 ms
111,216 KB
testcase_37 AC 499 ms
119,220 KB
testcase_38 AC 269 ms
93,520 KB
testcase_39 AC 560 ms
123,756 KB
testcase_40 AC 635 ms
101,492 KB
testcase_41 AC 394 ms
109,048 KB
testcase_42 AC 403 ms
107,260 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)}'
    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
    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_min()
    if w > a:
      return False
  for _ in range(m):
    a = A.pop_min()
    c = C.pop_min()
    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_min()
    if a > c:
      return False
  for _ in range(n):
    w = W.pop_min()
    a = A.pop_min()
    if w > a:
      return False
  return True

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