Bekzhan Kassenov

Задача №1.

Задача A. Очередь

Ограничение по времени:

1 секунда

Ограничение по памяти:

64 мегабайта

Бекжану рассказали об одной интересной очереди. Это очередь в кассу, в которой работает не особо добросовестный кассир. Кассир в этой очереди обслуживает клиента, только когда клиент ругается с ним. Время от времени кто-то из очереди осознает, что он опаздывает на очень важную встречу, проходит вне очереди, ругается с кассиром, после чего кассир его обслуживает. Допустим, что человека, прошедшего вне очереди зовут Ануар. Каждый человек, стоявший перед Ануаром в очереди, выразит свое недовольство его поступком в виде какого-то количества слов (фиксированного для каждого говорящего). Наблюдавшему за очередью Бекжану стало интересно, сколько же нелестных слов в свой адрес услышит каждый, прошедший вне очереди?

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

Первая строка входных данных содержит целое число

$N$ (

$2 \leq N \leq 5 \cdot 10^5$ ) — число событий в очереди. Описание каждого из событий начинается с целого числа

$type$ (

$1 \leq type \leq 2$ ). Если

$type = 1$ , то за ним следует целое число

$w$ (

$1 \leq w \leq 10^9$ ). Данный тип запросов означает, что новый человек пришел в очередь. Его номером является наименьшее целое положительное число, не использованное до этого в качестве номера, а количеством слов, которые он будет произносить при каждом недовольстве — число

$w$ . Если

$type = 2$ , то за ним следует целое число

$x$ . Данный тип запросов означает, что человек с номером

$x$ проходит вне очереди. Гарантируется, что в момент запроса человек с таким идентификатором присутствует в очереди. Гарантируется, что хотя бы один человек покинет очередь.

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

Для каждого прошедшего вне очереди человека выведите, сколько слов возмущения он услышит из очереди.

Система оценки

$N \le 20$ , $w \le 1000$ . Стоимость подгруппы: $10$ баллов.
$N \le 10000$ . Стоимость подгруппы: $40$ баллов.
$N \le 500000$ . Стоимость подгруппы: $50$ баллов.

Примеры:

Вход

2
1 1
2 1

Ответ

Вход

Ответ

8
19

Замечание

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

$8$ ,

$1$ и

$9$ слов недовольства соответственно (и получат номера

$1$ ,

$2$ и

$3$ соответственно). Затем человек с номером

$2$ пройдет вне очереди и выслушает недовольство от человека с номером

$1$ (

$8$ слов). После этого в очередь придут люди с количествами слов

$2$ и

$4$ , и номерами

$4$ и

$5$ соответственно. Затем человек с номером

$5$ пройдет вне очереди и выслушает недовольство от людей с номерами

$1$ ,

$3$ ,

$4$ (

$19$ слов). Последним в очередь придет человек с номером

$6$ и количеством слов

$3$ ( Bekzhan Kassenov )
комментарий/решение(1) олимпиада