Điểm:
600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Ơ trong 1 lần đi chơi với đám bạn (Khánh, Hòa, Khoa, Quân, Ngạn), cả 5 thanh niên này đều muốn chơi game, nhưng mà ai cũng không có tiền nhưng cạnh bên quán game lại có 1 cô gái tên là Thảo, cô gái này đưa ra nhưng bài toán, nếu giải được bài toán thì sẽ được thưởng 1 số tiền random(10K -> 100K), thế là 5 thanh niên này liền bắt tay vào giải bài toán để kiếm tiền chơi game. Nhưng bài toán quá khó, bạn có thể giải giúp 5 thanh niên này được không?
Cho 1 chuỗi kí tự \(S\) chỉ gồm kí tự '(' và ')' và \(m\) truy vấn, mỗi truy vấn là 2 số nguyên dương \(l , r \ (1 \leq l \leq r \leq S.size())\).
Lưu ý: \(S.size()\) là số lượng kí tự của chuỗi \(S\)
Yêu cầu: Hãy xác định dãy ngoặc đúng dài nhất trong đoạn \((l, r)\)
Input:
- Dòng thứ nhất là chuỗi kí tự \(S \ (1 \leq S.size() \leq 10^6)\)
- Dòng thứ 2 là số nguyên dương \(m\) là số lượng truy vấn \((1 \leq m \leq 10^5)\)
- \(m\) dòng tiếp theo là 2 số nguyên dương \(l, r \ (1 \leq l \leq r \leq S.size())\)
Output:
- m dòng số nguyên dương , tương ứng với kết quả của đáp án
Scoring:
- Subtask \(1\) (\(43.33\%\) số điểm): \(1 \leq S.size(), m \leq 1000\)
- Subtask \(1\) (\(56.67\%\) số điểm): không có ràng buộc gì thêm
Example
Test 1
Input
(((())((((()()((((((()((()(((((((((((()((
6
20 37
28 32
12 18
7 25
21 33
4 5
Output
4
0
2
6
4
2
Note
Trong truy vấn thứ 1 ta có chuỗi ((()((()(((((((((
, ta thấy chuỗi có dãy ngoặc đúng dài nhất là ()()
. Vậy kết quả là 4
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Tại sao em lại đi net?
hmu sao lại có tên em trong đề 🙁
bài này sol khá dài nên thôi nhường cho SPyofgame 🙂
quả chia subtask thú vị quá