Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2432. Скобки
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 02/11/2018 | Муниципальный этап 10-11 классы (4) |
| 27/11/2022 | Задачи из копилки МЭ (проводит sartasova) (G) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Хорошей последовательностью скобок будем называть последовательность из открывающихся и закрывающихся скобок,
в которой при последовательном чтении как слева направо, так и справа налево количество открывающихся скобок
остается больше или равно количества закрывающихся скобок.
Напишите программу, которая определяет минимальное количество закрывающихся скобок, которое нужно
удалить из последовательности скобок, чтобы она стала хорошей.
Первая строка ввода содержит одно целое число `N` — количество скобок. Вторая строка ввода содержит `N` открывающихся
и закрывающихся скобок. Третья строка содержит одно целое число `Q` – количество запросов. Далее следует `Q` строк,
в каждой строке содержится два целых числа `L_i`, `R_i` (`1\ ≤\ L_i\ ≤\ R_i\ ≤\ N`) – индекс начала и конца
подпоследовательности, которую нужно превратить в хорошую.
Для каждого запроса вывести на отдельной строке одно целое число – минимальное количество
закрывающихся скобок, которое нужно удалить из подпоследовательности скобок с `L_i` по `R_i`.
Пример ввода
11 ((())))))(( 3 1 11 4 9 1 6
Пример вывода
4 6 3
В первом запросе хорошей является последовательность "((())((", во втором запросе – "", в третьем – "(((".
Описание подзадач и системы оценивания
Подзадача 1 (25 баллов)
`1\ ≤\ N,\ Q\ ≤\ 2000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N,\ Q\ ≤\ 70000`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (25 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ N,\ Q\ ≤\ 500000`
В этой подзадаче 10 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
