Leaders
실버 I의견: 0
Farmer John has \(N\) cows (\(2 \leq N \leq 10^5\)). Each cow has a breed that is
either Guernsey or Holstein. As is often the case, the cows are standing in a
line, numbered \(1 \ldots N\) in this order.
Over the course of the day, each cow writes down a list of cows. Specifically,
cow \(i\)'s list contains the range of cows starting with herself (cow \(i\)) up to
and including cow \(E_i\) (\(i \leq E_i \leq N\)).
FJ has recently discovered that each breed of cow has exactly one distinct
leader. FJ does not know who the leaders are, but he knows that each leader must
have a list that includes all the cows of their breed, or the other breed's
leader (or both).
Help FJ count the number of pairs of cows that could be leaders. It is
guaranteed that there is at least one possible pair.
Problem credits: Mythreya Dharani
SCORING
- Inputs 3-5: \(N \leq 100\)
- Inputs 6-10: \(N \leq 3000\)
- Inputs 11-17: No additional constraints.
Problem credits: Mythreya Dharani
The first line contains \(N\).
The second line contains a string of length \(N\), with the \(i\)th character
denoting the breed of the \(i\)th cow (G meaning Guernsey and H meaning Holstein).
It is guaranteed that there is at least one Guernsey and one Holstein.
The third line contains \(E_1 \dots E_N\).
Output the number of possible pairs of leaders.
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
평가 및 의견
Leaders
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Leaders