結果

問題 No.2240 WAC
ユーザー titan23titan23
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
67,200 KB
testcase_01 AC 56 ms
67,328 KB
testcase_02 AC 56 ms
67,328 KB
testcase_03 AC 56 ms
66,688 KB
testcase_04 AC 56 ms
67,072 KB
testcase_05 AC 56 ms
67,200 KB
testcase_06 AC 57 ms
67,328 KB
testcase_07 AC 56 ms
67,584 KB
testcase_08 AC 58 ms
67,200 KB
testcase_09 AC 57 ms
67,456 KB
testcase_10 AC 233 ms
79,360 KB
testcase_11 WA -
testcase_12 AC 230 ms
79,300 KB
testcase_13 AC 162 ms
79,004 KB
testcase_14 AC 134 ms
78,592 KB
testcase_15 AC 198 ms
79,744 KB
testcase_16 WA -
testcase_17 AC 195 ms
78,848 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 203 ms
79,616 KB
testcase_21 WA -
testcase_22 AC 153 ms
78,976 KB
testcase_23 AC 159 ms
79,232 KB
testcase_24 AC 189 ms
79,116 KB
testcase_25 WA -
testcase_26 AC 159 ms
79,488 KB
testcase_27 AC 143 ms
78,908 KB
testcase_28 AC 156 ms
78,848 KB
testcase_29 AC 129 ms
79,104 KB
testcase_30 AC 164 ms
79,232 KB
testcase_31 AC 209 ms
79,744 KB
testcase_32 WA -
testcase_33 AC 174 ms
78,720 KB
testcase_34 AC 185 ms
79,360 KB
testcase_35 AC 131 ms
79,104 KB
testcase_36 WA -
testcase_37 AC 205 ms
79,740 KB
testcase_38 AC 149 ms
78,720 KB
testcase_39 AC 222 ms
79,232 KB
testcase_40 AC 168 ms
79,132 KB
testcase_41 AC 189 ms
79,872 KB
testcase_42 AC 189 ms
79,560 KB
権限があれば一括ダウンロードができます

ソースコード

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