Олимпиадный тренинг

Задача . D. Сосуды


Задача

Темы: Деревья реализация снм Структуры данных *1800

Есть система из n сосудов, расположенных один над другим так, как показано на рисунке ниже. Представим, что сосуды пронумерованы числами от 1 до n в порядке от самого верхнего к самому нижнему, объем i-го сосуда равен ai литров.

Изначально все сосуды пустые. В некоторые сосуды наливают воду, при этом вся вода, не поместившаяся в i-й сосуд, переливается в (i + 1)-й. Жидкость, не поместившаяся в n-й сосуд, выливается на пол.

Ваша задача состоит в том, чтобы промоделировать наливание воды в сосуды. Для этого вам потребуется обрабатывать два типа запросов:

  1. Долить в pi-й сосуд xi литров воды;
  2. Вывести, сколько воды находится в ki-м сосуде.

При ответе на второй запрос можно считать, что вся вода, налитая до этого момента, уже успела перелиться между сосудами.

Входные данные

В первой строке записано целое число n — количество сосудов (1 ≤ n ≤ 2·105). Во второй строке записаны n целых чисел a1, a2, ..., an — вместимости сосудов (1 ≤ ai ≤ 109). Вместимости сосудов не обязательно возрастают от верхних сосудов к нижним (см. второй пример). В третьей строке записано целое число m — количество запросов (1 ≤ m ≤ 2·105). Каждая из следующих m строк содержит описание одного запроса. Запрос первого типа задается как «1 pi xi», запрос второго типа — как «2 ki» (1 ≤ pi ≤ n, 1 ≤ xi ≤ 109, 1 ≤ ki ≤ n).

Выходные данные

На каждый запрос второго типа в отдельной строке выведите количество воды в соответствующем сосуде.


Примеры
№Входные данныеВыходные данные
1 2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2 
4
5
8
2 3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3 
7
10
5

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет