레이팅 미적용엘시는 베시에게 자신이 가장 좋아하는 USACO 대회를 설명하려 하지만, 베시는 엘시가 왜 그렇게 좋아하는지 이해하지 못하고 있다. 엘시는 이렇게 말한다. "And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO".
베시는 여전히 이해하지 못해서, 엘시의 설명을 소문자 알파벳으로 이루어진 길이 \(N\)(\(3 \leq N \leq 10^5\))의 문자열 \(s_1s_2 \ldots s_N\)으로 받아 적는다. 엘시는 세 문자로 이루어진 문자열 \(t\)가 \(t_2 = t_3\)이고 \(t_2 \neq t_1\)일 때 이를 moo라고 여긴다.
삼중쌍 \((i, j, k)\)는 \(i < j < k\)이고 문자열 \(s_i\ s_j\ s_k\)가 moo를 이룰 때 유효하다. 이 삼중쌍에 대해 농부 존은 다음과 같이 값을 계산한다.
- 농부 존은 문자열 \(s\)를 인덱스 \(j\)에서 90도로 구부린다
- 삼중쌍의 값은 \(\Delta ijk\) 넓이의 두 배이다.
다시 말해, 삼중쌍의 값은 \((j-i)(k-j)\)이다.
베시는 \(Q\)개(\(1 \leq Q \leq 3 \cdot 10^4\))의 쿼리를 묻는다. 각 쿼리에서 베시는 두 정수 \(l\)과 \(r\)(\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\))을 주고, \(l \leq i\)이고 \(k \leq r\)인 유효한 삼중쌍 \((i, j, k)\) 중 최대 값을 묻는다. 유효한 삼중쌍이 없으면 \(-1\)을 출력한다.
이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.
Problem credits: Chongtian Ma
배점
- 입력 2-3: \(N,Q\le 50\)
- 입력 4-6: \(Q=1\)이고 그 유일한 쿼리는 \(l=1\)과 \(r=N\)을 만족한다
- 입력 7-11: 추가 제약이 없다
Problem credits: Chongtian Ma
첫째 줄에 두 정수 \(N\)과 \(Q\)가 주어진다.
다음 줄에 \(s_1 s_2, \ldots s_N\)이 주어진다.
다음 \(Q\)개의 줄에 각 쿼리를 나타내는 두 정수 \(l\)과 \(r\)이 주어진다.
각 쿼리의 답을 새로운 줄에 출력한다.
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