結果

問題 No.2240 WAC
コンテスト
ユーザー titan23
提出日時 2023-03-11 11:20:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,681 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 79,872 KB
最終ジャッジ日時 2024-09-18 06:17:01
合計ジャッジ時間 7,876 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35 WA * 8
権限があれば一括ダウンロードができます

ソースコード

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})'

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

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_max()
    if w > a:
      return False
  for _ in range(m):
    a = A.pop_max()
    c = C.pop_max()
    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_max()
    c = C.pop_max()
    if a > c:
      return False
  for _ in range(n):
    w = W.pop_min()
    a = A.pop_max()
    if w > a:
      return False
  return True

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