Mùa Moo III

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Elsie mô tả một kỳ thi USACO bằng xâu $s$ độ dài $N$ gồm các chữ cái thường. Một "moo" là xâu ba ký tự $t$ thỏa mãn $t_{2} = t_{3}$ và $t_{2} \neq t_{1}$ .

Bộ ba $(i, j, k)$ với $i < j < k$ là hợp lệ nếu $s_{i} s_{j} s_{k}$ tạo thành một "moo". Giá trị của bộ ba đó là $(j - i) \times (k - j)$ .

Với $Q$ truy vấn, mỗi truy vấn cho $l$ và $r$ , tìm giá trị lớn nhất trong các bộ ba hợp lệ $(i, j, k)$ với $l \leq i$ và $k \leq r$ , hoặc trả về $- 1$ nếu không tồn tại.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $Q$ .
Dòng 2: Xâu $s$ độ dài $N$ .
$Q$ dòng tiếp theo: Hai số nguyên $l$ , $r$ .

Dữ liệu ra

$Q$ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Ràng buộc

$3 \leq N \leq 10^{5}$
$1 \leq Q \leq 3 \times 10^{4}$
$1 \leq l \leq r \leq N$ , $r - l + 1 \geq 3$

Ví dụ

Input	Output	Giải thích
12 5 abcabbacabac 1 12 2 7 4 8 2 5 3 10	28 6 1 -1 12	Truy vấn 1: Bộ ba tối ưu cho giá trị $(j - i) (k - j) = 28$ . Truy vấn 4: Không có "moo" hợp lệ trong đoạn [2,5].

Bình luận

Không có bình luận tại thời điểm này.