Задача D. Саша и кофе ≡

Условие

Программист Саша пьет кофе всегда из одной и той же кружки, которую он никогда не моет.

Когда кофе находится в кружке достаточно долго, оно оставляет на ней кофейное кольцо.

Иногда Саша подливает кофе в кружку, от чего уровень кофе поднимается, и все кольца, которые оказываются ниже уровня кофе растворяются.

Саша может выполнить 3 действия:

1. Налить в кружку coffee_i миллилитров кофе.
2. Выпить coffee_i миллилитров кофе.
3. Определить сколько кофейных колец сейчас на кружке.

Считаем, что после каждого действия Саши кофе в кружке стоит достаточно долго, чтобы кольцо успело образоваться.

Формат входных данных

Первая строка входных данных содержит число n - количество действий, которые сделал Саша.

В следующих n строках идет:

• + coffee_i - Саша доливает в кружку coffee_i миллилитров кофе.
• - coffee_i - Саша выливает из кружки coffee_i миллилитров кофе.

Гарантируется, что Саша не пытается выпить больше кофе, чем есть в кружке. Изначально в кружке нет ни миллилитра кофе.

Формат выходных данных

Требуется вывести количество кофейных колец, которое было на кружке после каждого действия Саши. Каждое в новой строке.

Ограничения

0 < n ≤ 10⁷

0 < с_i ≤ 10⁸

Гарантируется, что объем кофе в стакане никогда не достигнет 2³².

Примеры тестов

14
+ 108
+ 105
+ 110
+ 101
- 32
+ 32
+ 32
+ 32
+ 32
- 103
- 114
- 101
- 101
- 100

1
1
1
1
2
1
1
1
1
2
3
4
5
6

9
+ 1
- 1
+ 1
+ 1
+ 2
+ 3
- 4
+ 1
+ 7

1
1
1
1
1
1
2
2
1

Разбор

Идея решения:

Так как команды подаются раздельно друг от друга, то алгоритм решения не может быть быстрее, чем O(n).

Кольцо может образоваться только при изменении уровня кофе в кружке, и притом только 1 кольцо.

Давайте хранить кофейные кольца упорядочено по уровню.

Тогда, когда Саша доливает кофе нужно лишь перебрать кольца с наименьшим уровнем и стереть их.

А когда Саша выпивает кофе мы добавляем новое кольцо.

Однако нужно отдельно обработать, момент, когда кофе закончилось, так как тогда кольцо не образуется. И если Саша ничего не долил или ничего не выпил, тогда новое кольцо тоже не может появится.

Описание реализации:

Нам нужно упорядочено хранить кольца, для этого могут подойти: queue, set, stack. Но так как кольцо появляются последовательно и новое кольцо всегда меньше, чем предыдущее, нам хватит и stack.

rings - стэк, хранящий все кофейные кольца, которые есть сейчас. Кольцо определяется уровнем кофе, на котором оно появилось.

На дне stack будут кольца с большим уровнем, а наверху с наименьшим.

Когда приходит команда на изменение объема кофе, мы изменяем переменную с текущим уровнем кофе, назовем ее coffee.

Если мы долили кофе, то нужно выкинуть сверху rigns все кольца с объемом меньшим или равным текущему уровню. А в конце добавить кольцо текущего уровня.

Если же Саша выпил кофе, то добавляем новое кольцо.

Отдельно рассмотреть ситуации, про которые говорилось ранее.

Чтобы посчитать количество колец нам нужно лишь вернуть размер rings, это работает за O(1).