05. Серёжа и скобки#

📝 Условие#

Дана скобочная строка. Для каждого запроса [l, r] найдите длину самой длинной правильной скобочной подпоследовательности на отрезке.

📥 Входные данные#

В первой строке строка s из ( и ) (1 ≤ |s| ≤ 10⁶). Во второй — число m (1 ≤ m ≤ 10⁵). Далее m строк l r (1 ≤ l ≤ r ≤ |s|).

📤 Выходные данные#

m строк — ответы на запросы.

🧪 Тесты#

Тест 1#

Ввод:

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Вывод:

0
0
2
10
4
6
6

Тест 2#

Ввод:

()()
2
1 4
2 3

Вывод:

4
0

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня