Билеты на «Бишкек Арену»


Отправить решение Решать в редакторе

Сложность: 75%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

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 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.