Tổng Ngoặc Đúng

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
algorit
Dạng bài
Đ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