Билеты на «Бишкек Арену»
31 августа 2026 года церемонией открытия VI Всемирных игр кочевников начал работу новый стадион «Бишкек Арена». Его чаша, выполненная в форме кыргызской юрты, вмещает более 50 тысяч зрителей.
Нурбек пишет систему продажи билетов на верхний ярус. Ярус — это одно кольцо из n кресел, пронумерованных по часовой стрелке от 1 до n; кресло n стоит рядом с креслом 1. Перед началом продаж все кресла свободны. Поступает q событий:
+ k— компания изkдрузей хочет сидеть рядом: нужно найтиkподряд идущих по кольцу свободных кресел. Из всех подходящих блоков выбирается тот, у которого номер первого (по часовой стрелке) кресла наименьший. Кресла блока становятся занятыми, а система выводит номер первого кресла. Если подходящего блока нет, выводится0и ничего не меняется;- l r— компания сдала билеты: все кресла отlдоrпо часовой стрелке (включительно) становятся свободными. Еслиl > r, отрезок проходит через стык креселnи1. Некоторые из этих кресел могли быть свободны и раньше;? l r— нужно вывести количество свободных кресел на отрезке отlдоrпо часовой стрелке (по тем же правилам).
Обратите внимание: блок из примера ниже, начинающийся с кресла 9, — это кресла 9, 10, 1, 2, 3.
Входные данные
В первой строке — два целых числа n и q (1 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 300 000).
В каждой из следующих q строк — одно событие в описанном формате (1 ≤ k ≤ 2 000 000, 1 ≤ l, r ≤ n).
Выходные данные
Для каждого события вида + и ? выведите ответ в отдельной строке.
Пример 1
Вход:
10 9
+ 4
+ 3
+ 4
- 2 3
? 1 10
+ 3
- 9 2
+ 5
? 8 3
Выход:
1
5
0
5
8
9
0
Пояснение
Первые две компании занимают кресла 1–4 и 5–7. Для третьей компании свободны только кресла 8–10, поэтому ответ 0. После возврата билетов на кресла 2–3 свободно пять кресел, и компания из трёх человек получает кресла 8–10. После возврата кресел 9, 10, 1, 2 свободны кресла 9, 10, 1, 2, 3 — ровно один блок из пяти кресел через стык, он начинается с кресла 9.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | n, q ≤ 2000 |
| 2 | 20 | нет событий вида - |
| 3 | 60 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии