Задача №114671. Ремонт дороги
Наступила осень, стали лить дожди, а коммунальные службы Берляндии начали ремонт дорог. В результате многочисленных дорожных реформ Берляндии, в ней осталась только одна дорога, которая состоит из участков, последовательно пронумерованных целыми числами от \(-10^9\) до \(10^9\). Решено было ремонтировать некоторые участки главной дороги Берляндии на отрезке с \(l\)-го по \(r\)-й. К сожалению, иногда некоторые участки дорог затапливаются дождями, поэтому ремонт таких участков дорог невозможен.
Изначально уровень воды на каждом участке дороги равен \(0\). Далее происходят \(n\) событий:
- Ремонтные службы хотят узнать, можно ли ремонтировать \(x\)-й участок дороги. Для этого им нужно узнать текущий уровень воды на \(x\)-м участке дороги.
-
Проходит ливень над \(x\)-м участком дороги, в результате чего уровень воды на нём увеличивается на \(1\).
Если после этого где-то уровень воды поднялся до \(2\), то вода начинает перетекать. На каждом участке дороги с номером \(i\), где уровень воды был \(2\), он опускается до \(0\), а на участках с номерами \(i - 1\) и \(i + 1\) уровень воды увеличивается на \(1\). Все такие перетекания происходят одновременно. Если после этого на каких-то участках уровень воды снова поднялся до \(2\), то процесс повторяется одновременно для них всех и продолжается до тех пор, пока на всех участках уровень воды не будет меньше \(2\). Можно показать, что такой процесс завершится, а также что никогда промежуточный уровень воды не поднимется выше \(2\). Следующее событие произойдёт только после окончания всех перетеканий. Также гарантируется, что вода никогда не вытечет за пределы участков дороги с \(l\)-го по \(r\)-й.
Вам необходимо ответить на все запросы первого типа.
Первая строка входных данных содержит три целых числа \(n\), \(l\) и \(r\) (\(1 \le n \le 200\,000\), \(-10^9 \le l \le r \le 10^9\)) — количество запросов и ограничения на номера участков из запросов.
В следующих \(n\) строках вводятся по символу \(c_i\) и целому числу \(x_i\) (\(l \le x_i \le r\)).
- Если \(c_i\) равняется « ? », то в \(i\)-м запросе требуется определить уровень воды на \(x_i\)-м участке дороги.
- Если \(c_i\) равняется « + », то в \(i\)-м запросе уровень воды на \(x_i\)-м участке увеличивается на единицу.
Гарантируется, что вода никогда не вытечет за пределы отрезка \([l, r]\).
Для каждого запроса первого типа в отдельной строке выведите одно целое число (\(0\) или \(1\)) — уровень воды на участке из запроса.
Тесты к этой задаче состоят из 4 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(l\) | \(r\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 26 | \(n \le 100\) | \(l = 0\) | \(r = 100\) | – | |
| 2 | 21 | \(n \le 1000\) | \(l = -10^9\) | \(r = 10^9\) | 0, 1 | |
| 3 | 22 | \(n \le 10\,000\) | \(l = 0\) | \(r = 1000\) | 1 | |
| 4 | 31 | – | \(l = -10^9\) | \(r = 10^9\) | 0, 1, 2, 3 | Offline-проверка. |
5 0 2 + 1 + 1 ? 0 ? 1 ? 2
1 0 1
7 0 4 + 1 + 2 + 3 + 2 ? 0 ? 2 ? 4
1 0 1
10 -5 5 + 0 + -1 + 1 ? -2 ? 0 + -1 ? -1 ? 0 ? 1 ? 2
0 1 1 1 0 1