레이팅 미적용농부 존에게는 \(N\)마리의 소가 있다 (\(2 \leq N \leq 10^5\)). 각 소의 품종은 건지(Guernsey) 또는 홀스타인(Holstein)이다. 흔히 그렇듯, 소들은 한 줄로 서 있으며 이 순서대로 \(1 \ldots N\)의 번호가 매겨져 있다.
하루 동안 각 소는 소들의 목록을 적는다. 구체적으로, 소 \(i\)의 목록은 자기 자신(소 \(i\))부터 소 \(E_i\)까지(\(i \leq E_i \leq N\))의 범위의 소들을 포함한다.
농부 존은 최근 각 품종마다 정확히 한 마리의 서로 다른 리더가 있다는 사실을 알아냈다. 그는 리더가 누구인지는 모르지만, 각 리더의 목록에는 자기 품종의 모든 소가 포함되거나, 다른 품종의 리더가 포함되거나 (혹은 둘 다) 해야 한다는 것을 알고 있다.
리더가 될 수 있는 소의 쌍의 수를 세도록 농부 존을 도와주자. 가능한 쌍이 적어도 하나 존재함이 보장된다.
Problem credits: Mythreya Dharani
채점 방식
- 입력 3-5: \(N \leq 100\)
- 입력 6-10: \(N \leq 3000\)
- 입력 11-17: 추가 제약이 없다.
Problem credits: Mythreya Dharani
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 길이 \(N\)의 문자열이 주어지며, \(i\)번째 문자는 \(i\)번째 소의 품종을 나타낸다 (G는 건지, H는 홀스타인). 건지와 홀스타인이 각각 적어도 한 마리씩 있음이 보장된다.
셋째 줄에 \(E_1 \dots E_N\)이 주어진다.
가능한 리더 쌍의 수를 출력한다.
4
GHHG
2 4 3 41The only valid leader pair is \((1, 2)\). Cow \(1\)'s list contains the other
breed's leader (cow \(2\)). Cow \(2\)'s list contains all cows of her breed
(Holstein).
No other pairs are valid. For example, \((2,4)\) is invalid since cow \(4\)'s list
does not contain the other breed's leader, and it also does not contain all cows
of her breed.
3
GGH
2 3 32There are two valid leader pairs, \((1, 3)\) and \((2, 3)\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Bronze