G. Старый стек

Имя входного файла:	stack.in
Имя выходного файла:	stack.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

Однако стек в программе Валеры оказался настолько старым, что в нем образовались дыры, в которые элементы могут самопроизвольно вываливаться. Более формально, в стеке есть N дыр, каждая из которых находится на высоте h_i, а элемент в неё вываливается, если над ним находится минимум a_i элементов. Все элементы вываливаются одновременно (то есть если после добавления очередного элемента несколько элементов должны вывалиться в дыру, то они вывалятся все).

Помогите Валере по описанию стека и списку операций над ним понять, сколько элементов будет безвозвратно утеряно через дыры в стеке.

Формат входного файла

Первая строка входного файла содержит два целых числа N и M(1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 3 *10⁵) – количество дыр в стеке и количество операций, соответственно. В последующих N строках находится по два числа – 1 ≤ a_i ≤ 3 *10⁵ и 1 ≤ h_i ≤ 3 *10⁵ – описание i-той дыры в стеке. В следующей строке содержится M символов + и -. Символ + обозначает операцию добавления элемента в стек, символ - – операцию удаления.

Формат выходного файла

В выходной файл выведите единственное число – количество предметов, вывалившихся через дыры.

Пример:

stack.in	stack.out
2 4 1 1 2 1 +++-	2
2 5 1 2 2 1 +++++	4

Рассмотрим первый пример:

1. Добавление. В стеке один элемент.
2. Добавление. В стеке два элемента. Один элемент вываливается в дыру на высоте 1 (поскольку над ним оказывается один элемент). Остается один элемент.
3. Добавление. Так же, как и на прошлом шаге, один элемент вываливается. Остается один элемент.
4. Удаление.

Таким образом, потеряется два элемента.

Рассмотрим второй пример:

1. Добавление. В стеке один элемент.
2. Добавление. В стеке два элемента. Элемент в дыру на высоте 1 не вываливается, поскольку над ним только один элемент, а в описании дыры указано, что требуется не менее двух.
3. Добавление. В стеке три элемента. Вываливается элемент в дыру на высоте 1 (потому что над ним оказывается два элемента). И вываливается элемент в дыру на высоте 2 (потому что над ним один элемент, а вываливаются элементы одновременно). В стеке остаётся один элемент.
4. Так же, как на шаге 2.
5. Так же, как на шаге 3.

Таким образом, потеряется четыре элемента.

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати