Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Горы мусора

(Время: 1 сек. Память: 32 Мб Сложность: 26%)

Недавно Виталя во время прогулки шел мимо свалки и заметил, что мусор на ней сортируется на n типов. Каждый из типов мусора лежит в своей куче, и изначально в i-й куче находится ai единиц мусора. Виталя заметил, что когда мусора становится так много, что его видно из-за забора, то это уже не куча мусора, а целая гора! Такая ситуация происходит, когда в куче присутствует хотя бы m единиц мусора.

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

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

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

В первой строке входного файла INPUT.TXT содержатся два целых числа n и m (1 ≤ n ≤ 2×105; 1 ≤ m ≤ 109) – количество типов мусора и минимальное количество мусора в горе соответственно.

Во второй строке содержатся n целых чисел ai (1 ≤ ai ≤ 109) – начальные размеры куч мусора.

В третьей строке содержится целое число k (1 ≤ k ≤ 2×105) – количество операций изменения.

В каждой из следующих k строк содержатся два целых числа t и x (1 ≤ t ≤ n; −109 ≤ x ≤ 109) – тип мусора и изменение количества мусора этого типа соответственно.

Гарантируется, что после каждой операции в каждой куче будет содержаться неотрицательное количество мусора.

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

В выходной файл OUTPUT.TXT после каждой операции изменения в отдельную строку выведите сумму гор мусора на текущий момент.

Пример

INPUT.TXTOUTPUT.TXT
15 4
1 2 3 4 5
2
1 2
5 -3
9
4

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

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 A. Забытая цифра
 B. Число + олсич
 C. Соревнование кузнечиков
 D. Два квадрата
 E. Горы мусора
 F. Урок физкультуры
 G. Игра в монетку
 H. Снеговик
 I. Сплетня
 J. Кластеры

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru