It's Mooin' Time III
브론즈 II의견: 0
Elsie is trying to describe her favorite USACO contest to Bessie, but Bessie is
having trouble understanding why Elsie likes it so much. Elsie says "And It's
mooin' time! Who wants a mooin'? Please, I just want to do USACO".
Bessie still doesn't understand, so she transcribes Elsie's description in a
string of length \(N\) (\(3 \leq N \leq 10^5\)) containing lowercase alphabetic
characters \(s_1s_2 \ldots s_N\). Elsie considers a string \(t\) containing three
characters a moo if \(t_2 = t_3\) and \(t_2 \neq t_1\).
A triplet \((i, j, k)\) is valid if \(i < j < k\) and string \(s_i\ s_j\ s_k\) forms a
moo. For the triplet, FJ performs the following to calculate its value:
- FJ bends string \(s\) 90-degrees at index \(j\)
- The value of the triplet is twice the area of \(\Delta ijk\).
In other words, the value of the triplet is \((j-i)(k-j)\).
Bessie asks you \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) queries. In each query, she
gives you two integers \(l\) and \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) and
ask you for the maximum value among valid triplets \((i, j, k)\) such that
\(l \leq i\) and \(k \leq r\). If no valid triplet exists, output \(-1\).
Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).
Problem credits: Chongtian Ma
SCORING
- Inputs 2-3: \(N,Q\le 50\)
- Inputs 4-6: \(Q=1\) and the singular query satisfies \(l=1\) and \(r=N\)
- Inputs 7-11: No additional constraints
Problem credits: Chongtian Ma
The first line contains two integers \(N\) and \(Q\).
The following line contains \(s_1 s_2, \ldots s_N\).
The following \(Q\) lines contain two integers \(l\) and \(r\), denoting each query.
Output the answer for each query on a new line.
12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 1028
6
1
-1
12For the first query, (\(i,j,k\)) must satisfy \(1 \le i < j < k \le 12\). It can be
shown that the maximum area of \(\Delta ijk\) for some valid (\(i,j,k\)) is achieved
when \(i=1\), \(j=8\), and \(k=12\). Note that \(s_1\ s_8\ s_{12}\) is the string "acc"
which is a moo according to the definitions above. \(\Delta ijk\) will have legs
of lengths \(7\) and \(4\) so two times the area of it will be \(28\).
For the third query, (\(i,j,k\)) must satisfy \(4 \le i < j < k \le 8\). It can be
shown that the maximum area of \(\Delta ijk\) for some valid (\(i,j,k\)) is achieved
when \(i=4\), \(j=5\), and \(k=6\).
For the fourth query, there exists no (\(i,j,k\)) satisfying
\(2 \le i < j < k \le 5\) in which \(s_i\ s_j\ s_k\) is a moo so the output to that
query is \(-1\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Bronze
평가 및 의견
It's Mooin' Time III
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
It's Mooin' Time III