Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В городе Кольцово есть только одна дорога, имеющая форму кольца и разделенная на `N` участков.
Участки дороги иногда ремонтируются и на это время проезд по ним невозможен.
Чтобы помочь жителям, вы должны написать программу, в которую поступает информация
о начале или окончании ремонта участков дороги и запросы о возможности проехать из дома, расположенного на
участке `A`, в дом, расположенный на участке `B`. Если участок, на котором расположен дом,
ремонтируется, то нельзя ни выехать с него, ни приехать на него.
Первая строка ввода содержит одно целое число `N` (`2 <= N <= 10^9`) – количество участков на дороге.
Вторая строка ввода содержит одно целое число `Q` (`1 <= Q <= 10^5`) – количество запросов.
Далее следует `Q` строк, каждая строка содержит запрос одного из следующих видов:
Вид запроса|Описание
--|--
+ `A`|Начался ремонт участка дороги с номером `A`. Гарантируется, что этот участок в момент запроса не ремонтируется.
- `A`|Закончился ремонт участка дороги с номером `A`. Гарантируется, что этот участок в момент запроса ремонтируется.
? `A` `B`|Запрос о возможности проезда из дома, расположенного на участке `A`, в дом, расположенный на участке `B`.
Здесь `A` и `B` – целые числа в диапазоне от 1 до `N`, `A != B`.
На каждый запрос вида ? `A` `B` вывести строку, содержащую одно целое число. Если проезд не возможен, то вывести число -1.
Если проезд возможен, то вывести минимальное расстояние (в участках), которое нужно проехать, чтобы добраться до участка `B`.
Например, расстояние между участком 1 и 2 равно 1, расстояние между участком `N` и 1 тоже равно 1, так как дорога имеет форму кольца.
```sample Пример ввода 1
10
2
? 1 2
? 1 9
```
```sample Пример вывода 1
1
2
```
```sample Пример ввода 2
10
8
+ 10
? 1 9
? 1 10
+ 5
? 1 9
? 4 1
- 10
? 1 9
```
```sample Пример вывода 2
8
-1
-1
3
2
```
Пример ввода 2 не включен в набор тестов из условия, так как он выходит за ограничения подзадач 1 и 2.
При решении подзадачи 3 вы должны проверить его самостоятельно.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (20 баллов)||
`2 <= N <= 1000`, `1 <= Q <= 10`, есть только запросы вида ? `A` `B`
В этой подзадаче 2 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 2 (20 баллов)||
`2 <= N <= 1000`, `2 <= Q <= 10`, первый запрос имеет вид + `A`, остальные – вид ? `A` `B`
Необходимые подзадачи: 1.
В этой подзадаче 2 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 3 (40 баллов)||
`2 <= N <= 1000`, `2 <= Q <= 1000`, могут быть все виды запросов.
Необходимые подзадачи: 1, 2.
В этой подзадаче 8 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 4 (20 баллов)||
`1000 < N <= 10^9`, `1000 < Q <= 10^5`, могут быть все виды запросов.
Необходимые подзадачи: 1, 2, 3.
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
Начало
Рабочее место участника
Деревья (map, set), хэш-таблицы