Задача B.
Ремонт дороги
Имя входного файла: стандартный ввод или input.txt
Имя выходного файла: стандартный вывод или output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Наступила осень, стали лить дожди, а коммунальные службы Берляндии начали ремонт дорог. В результате многочисленных дорожных реформ Берляндии, в ней осталась только одна дорога, которая состоит из участков, последовательно пронумерованных целыми числами от −109 до 109 . Решено было ремонтировать некоторые участки главной дороги Берляндии на отрезке с l-го по rй. К сожалению, иногда некоторые участки дорог затапливаются дождями, поэтому ремонт таких участков дорог невозможен.
Изначально уровень воды на каждом участке дороги равен 0. Далее происходят n событий:
1. Ремонтные службы хотят узнать, можно ли ремонтировать x-й участок дороги. Для этого им нужно узнать текущий уровень воды на x-м участке дороги.
2. Проходит ливень над x-м участком дороги, в результате чего уровень воды на нём увеличивается на 1.
Если после этого где-то уровень воды поднялся до 2, то вода начинает перетекать. На каждом участке дороги с номером i, где уровень воды был 2, он опускается до 0, а на участках с номерами i − 1 и i + 1 уровень воды увеличивается на 1. Все такие перетекания происходят одновременно. Если после этого на каких-то участках уровень воды снова поднялся до 2, то процесс повторяется одновременно для них всех и продолжается до тех пор, пока на всех участках уровень воды не будет меньше 2. Можно показать, что такой процесс завершится, а также что никогда промежуточный уровень воды не поднимется выше 2. Следующее событие произойдёт только после окончания всех перетеканий. Также гарантируется, что вода никогда не вытечет за пределы участков дороги с l-го по r-й.
Вам необходимо ответить на все запросы первого типа.
Формат входных данных
Первая строка входных данных содержит три целых числа n, l и r (1 6 n 6 200 000, −109 6 l 6 r 6 109 ) — количество запросов и ограничения на номера участков из запросов. В следующих n строках вводятся по символу ci и целому числу xi (l 6 xi 6 r).
• Если ci равняется «?», то в i-м запросе требуется определить уровень воды на xi-м участке дороги.
• Если ci равняется «+», то в i-м запросе уровень воды на xi-м участке увеличивается на единицу. Гарантируется, что вода никогда не вытечет за пределы отрезка [l, r].
Формат выходных данных
Для каждого запроса первого типа в отдельной строке выведите одно целое число (0 или 1) — уровень воды на участке из запроса.
Примеры
стандартный ввод | стандартный вывод
5 0 2 | 1 0 1
+ 1
+ 1
? 0
? 1
? 2
7 0 4 | 1 0 1
+ 1
+ 2
+ 3
+ 2
? 0
? 2
? 4
Ремонт дороги
Имя входного файла: стандартный ввод или input.txt
Имя выходного файла: стандартный вывод или output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Наступила осень, стали лить дожди, а коммунальные службы Берляндии начали ремонт дорог. В результате многочисленных дорожных реформ Берляндии, в ней осталась только одна дорога, которая состоит из участков, последовательно пронумерованных целыми числами от −109 до 109 . Решено было ремонтировать некоторые участки главной дороги Берляндии на отрезке с l-го по rй. К сожалению, иногда некоторые участки дорог затапливаются дождями, поэтому ремонт таких участков дорог невозможен.
Изначально уровень воды на каждом участке дороги равен 0. Далее происходят n событий:
1. Ремонтные службы хотят узнать, можно ли ремонтировать x-й участок дороги. Для этого им нужно узнать текущий уровень воды на x-м участке дороги.
2. Проходит ливень над x-м участком дороги, в результате чего уровень воды на нём увеличивается на 1.
Если после этого где-то уровень воды поднялся до 2, то вода начинает перетекать. На каждом участке дороги с номером i, где уровень воды был 2, он опускается до 0, а на участках с номерами i − 1 и i + 1 уровень воды увеличивается на 1. Все такие перетекания происходят одновременно. Если после этого на каких-то участках уровень воды снова поднялся до 2, то процесс повторяется одновременно для них всех и продолжается до тех пор, пока на всех участках уровень воды не будет меньше 2. Можно показать, что такой процесс завершится, а также что никогда промежуточный уровень воды не поднимется выше 2. Следующее событие произойдёт только после окончания всех перетеканий. Также гарантируется, что вода никогда не вытечет за пределы участков дороги с l-го по r-й.
Вам необходимо ответить на все запросы первого типа.
Формат входных данных
Первая строка входных данных содержит три целых числа n, l и r (1 6 n 6 200 000, −109 6 l 6 r 6 109 ) — количество запросов и ограничения на номера участков из запросов. В следующих n строках вводятся по символу ci и целому числу xi (l 6 xi 6 r).
• Если ci равняется «?», то в i-м запросе требуется определить уровень воды на xi-м участке дороги.
• Если ci равняется «+», то в i-м запросе уровень воды на xi-м участке увеличивается на единицу. Гарантируется, что вода никогда не вытечет за пределы отрезка [l, r].
Формат выходных данных
Для каждого запроса первого типа в отдельной строке выведите одно целое число (0 или 1) — уровень воды на участке из запроса.
Примеры
стандартный ввод | стандартный вывод
5 0 2 | 1 0 1
+ 1
+ 1
? 0
? 1
? 2
7 0 4 | 1 0 1
+ 1
+ 2
+ 3
+ 2
? 0
? 2
? 4