레이팅 미적용베시는 세 문자 'C', 'O', 'W'로만 이루어진, 길이가 최대 \(2 \cdot 10^5\)인 문자열 \(s\)를 발견한다. 베시는 다음 연산들을 사용하여 이 문자열을 (자신이 가장 좋아하는 문자인) 'C' 하나로 만들 수 있는지 알고 싶다.
-
인접한 같은 문자 두 개를 골라 삭제한다.
-
문자 하나를 골라, 나머지 두 문자로 (순서는 상관없이) 바꾼다.
문자열 자체에 대한 답만으로는 충분하지 않아서, 베시는 \(s\)의 \(Q\)개(\(1\le Q\le 2\cdot 10^5\)) 부분 문자열에 대한 답을 알고 싶어 한다.
Problem credits: Ray Bai
채점 방식
- 테스트 케이스 2-4는 \(|s|\le 5000\)이고 \(Q\le 5000\)을 만족한다.
- 테스트 케이스 5-11은 추가 제약이 없다.
Problem credits: Ray Bai
첫째 줄에 \(s\)가 주어진다.
다음 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에는 두 정수 \(l\)과 \(r\)이 주어진다(\(1\le l\le r\le |s|\), 여기서 \(|s|\)는 \(s\)의 길이를 나타낸다).
길이 \(Q\)의 문자열을 출력한다. \(i\)번째 문자는 \(i\)번째 부분 문자열을 줄일 수 있으면 'Y', 그렇지 않으면 'N'이다.
COW
6
1 1
1 2
1 3
2 2
2 3
3 3YNNNYNThe answer to the first query is yes because the first character of \(s\)
is already equal to 'C'.
The answer to the fifth query is yes because the substring OW from
the second to the third character of \(s\) can be
converted into 'C' in two operations:
OW
-> CWW
-> C
No other substring of this example string COW can be reduced to 'C'
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Silver