| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 104 | 37 | 31 | 37.349% |
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:
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++).
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 10
28 6 1 -1 12
For 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$.