結果

問題 No.2240 WAC
コンテスト
ユーザー titan23
提出日時 2023-03-11 12:36:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 374 ms / 2,000 ms
コード長 7,917 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 80,128 KB
最終ジャッジ日時 2024-09-18 06:18:09
合計ジャッジ時間 8,651 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# WordsizeTreeSet / WordsizeTreeMultiset
# 
# 0以上u未満の整数を管理できるset/multiset
# 32分木をList[List[int]]で実装している
# 空間O(u)であることに注意
# 
# 以下のだいたいの操作がO(logu)で可能
# add / discard / contains /
# ge / gt / le / lt / 
# get_min / get_max / pop_min / pop_max /
# clear(O(nlogu)) /
# len(O(1)) / iter / str / repr /
# 
# multisetは追加で
# count / keys / values / items /
# の機能がある
# データの個数はHashテーブルを用いて空間O(n)で管理している

from array import array
from typing import Iterable, TypeVar, Optional

class WordsizeTreeSet:

  def __init__(self, u: int, a: Iterable[int]=[]):
    self.u = u
    data = []
    len_ = 0
    if a:
      u >>= 5
      A = array('I', bytes(4*(u+1)))
      for a_ in a:
        if A[a_>>5] >> (a_&31) & 1 == 0:
          len_ += 1
          A[a_>>5] |= 1 << (a_&31)
      data.append(A)
      while u:
        a = array('I', bytes(4*((u>>5)+1)))
        for i in range(u+1):
          if A[i]:
            a[i>>5] |= 1 << (i&31)
        data.append(a)
        A = a
        u >>= 5
    else:
      while u:
        u >>= 5
        data.append(array('I', bytes(4*(u+1))))
    self.data = data
    self.len = len_
    self.len_data = len(data)

  def add(self, x: int) -> bool:
    if self.data[0][x>>5] >> (x&31) & 1: return False
    for a in self.data:
      a[x>>5] |= 1 << (x&31)
      x >>= 5
    self.len += 1
    return True

  def discard(self, x: int) -> bool:
    if self.data[0][x>>5] >> (x&31) & 1 == 0: return False
    self.len -= 1
    for a in self.data:
      a[x>>5] &= ~(1 << (x&31))
      x >>= 5
      if a[x]: break
    return True

  def ge(self, x: int) -> Optional[int]:
    d = 0
    data = self.data
    while True:
      if d >= self.len_data or x>>5 >= len(data[d]): return None
      m = data[d][x>>5] & ((~0) << (x&31))
      if m == 0:
        d += 1
        x = (x >> 5) + 1
      else:
        x = (x >> 5 << 5) + (m & -m).bit_length() - 1
        if d == 0: break
        x <<= 5
        d -= 1
    return x

  def gt(self, x: int) -> Optional[int]:
    return self.ge(x + 1)

  def le(self, x: int) -> Optional[int]:
    d = 0
    data = self.data
    while True:
      if x < 0 or d >= self.len_data: return None
      m = data[d][x>>5] & ~((~1) << (x&31))
      if m == 0:
        d += 1
        x = (x >> 5) - 1
      else:
        x = (x >> 5 << 5) + m.bit_length() - 1
        if d == 0: break
        x <<= 5
        x += 31
        d -= 1
    return x

  def lt(self, x: int) -> Optional[int]:
    return self.le(x - 1)

  def get_min(self) -> Optional[int]:
    return self.ge(0)

  def get_max(self) -> Optional[int]:
    return self.le(self.u - 1)

  def pop_min(self) -> int:
    assert self, 'IndexError: pop_min from empty WordsizeTreeSet.'
    v = self.get_min()
    self.discard(v)
    return v

  def pop_max(self) -> int:
    assert self, 'IndexError: pop_max from empty WordsizeTreeSet.'
    v = self.get_max()
    self.discard(v)
    return v

  def clear(self) -> None:
    for e in self:
      self.discard(e)
    self.len = 0

  def __bool__(self):
    return self.len > 0

  def __len__(self):
    return self.len

  def __contains__(self, x: int):
    return self.data[0][x>>5] >> (x&31) & 1 == 1

  def __iter__(self):
    self._val = self.ge(0)
    return self

  def __next__(self):
    if self._val is None:
      raise StopIteration
    pre = self._val
    self._val = self.gt(pre)
    return pre

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

  def __repr__(self):
    return f'WordsizeTreeSet({self})'


from array import array
from typing import Iterable, TypeVar, Optional

class WordsizeTreeMultiset:

  def __init__(self, u: int, a: Iterable[int]=[]):
    self.len = 0
    self.set = WordsizeTreeSet(u, a)
    cnt = {}
    for a_ in a:
      self.len += 1
      if a_ in cnt:
        cnt[a_] += 1
      else:
        cnt[a_] = 1
    self.cnt = cnt

  def add(self, x: int, val: int=1) -> None:
    self.len += val
    if x in self.cnt:
      self.cnt[x] += val
    else:
      self.cnt[x] = val
      self.set.add(x)

  def discard(self, x: int, val: int=1) -> bool:
    if x not in self.cnt: return False
    v = self.cnt[x]
    if v > val:
      self.cnt[x] -= val
      self.len -= val
    else:
      self.len -= v
      del self.cnt[x]
      self.set.discard(x)
    return True

  def count(self, x: int) -> int:
    return self.cnt[x] if x in self.cnt else 0

  def ge(self, x: int) -> Optional[int]:
    return self.set.ge(x)

  def gt(self, x: int) -> Optional[int]:
    return self.ge(x + 1)

  def le(self, x: int) -> Optional[int]:
    return self.set.le(x)

  def lt(self, x: int) -> Optional[int]:
    return self.le(x - 1)

  def get_min(self) -> Optional[int]:
    return self.set.ge(0)

  def get_max(self) -> Optional[int]:
    return self.set.le(self.set.u - 1)

  def pop_min(self) -> int:
    assert self, 'IndexError: pop_min from empty WordsizeTreeMultiset.'
    d, x = 0, 0
    ssd = self.set.data
    while True:
      m = ssd[d][x>>5] & ((~0) << (x&31))
      if m == 0:
        d += 1
        x = (x >> 5) + 1
      else:
        x = (x >> 5 << 5) + (m & -m).bit_length() - 1
        if d == 0: break
        x <<= 5
        d -= 1
    self.discard(x)
    return x

  def pop_max(self) -> int:
    assert self, 'IndexError: pop_max from empty WordsizeTreeMultiset.'
    d = 0
    ssd = self.set.data
    x = self.set.u - 1
    while True:
      m = ssd[d][x>>5] & ~((~1) << (x&31))
      if m == 0:
        d += 1
        x = (x >> 5) - 1
      else:
        x = (x >> 5 << 5) + m.bit_length() - 1
        if d == 0: break
        x <<= 5
        x += 31
        d -= 1
    self.discard(x)
    return x

  def keys(self):
    v = self.set.get_min()
    while v is not None:
      yield v
      v = self.set.gt(v)

  def values(self):
    v = self.set.get_min()
    while v is not None:
      yield self.cnt[v]
      v = self.set.gt(v)

  def items(self):
    v = self.set.get_min()
    while v is not None:
      yield (v, self.cnt[v])
      v = self.set.gt(v)

  def clear(self) -> None:
    for e in self:
      self.set.discard(e)
    self.len = 0
    self.cnt.clear()

  def __contains__(self, x: int):
    return x in self.cnt

  def __bool__(self):
    return self.len > 0

  def __len__(self):
    return self.len

  def __iter__(self):
    self.__val = self.set.get_min()
    self.__valcnt = 1
    return self

  def __next__(self):
    if self.__val is None:
      raise StopIteration
    pre = self.__val
    self.__valcnt += 1
    if self.__valcnt > self.cnt[self.__val]:
      self.__valcnt = 1
      self.__val = self.gt(self.__val)
    return pre

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

  def __repr__(self):
    return 'WordsizeTreeMultiset(' + str(self) + ')'

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

n, m = map(int, input().split())
s = input()
def solve1():
  W = WordsizeTreeSet(len(s))
  A = WordsizeTreeSet(len(s))
  C = WordsizeTreeSet(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 = WordsizeTreeSet(len(s))
  A = WordsizeTreeSet(len(s))
  C = WordsizeTreeSet(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