Ловушка для Джерри

Том наконец-то смог поймать Джерри в ловушку. Ловушка представляет из себя резервуар с
водой, в котором закреплены n платформ. Платформа с номером i находится на высоте ai относительно уровня воды в резервуаре.
Каждая платформа представляет определенный уровень опасности для Джерри. Если высота
платформы ai < 0, то платформа погружена под воду, и представляет опасность −ai. Если же ai > 0, то с платформы можно упасть, и ее опасность равна ai. Таким образом, опасность i-й платформы равна в точности |ai|.

У Тома есть доступ к панели управления платформами, которая позволяет ему изменить высоты
всех платформ на одно и то же число x, то есть новая высота i-й платформы станет равна ai + x.
Пока Джерри не выбрался из ловушки, Том успеет k раз воспользоваться панелью управления.
Ваша задача — после каждого действия Тома посчитать суммарную опасность ловушки, то есть
сумму опасностей всех платформ.

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

В первой строке ввода дано целое число n — количество платформ в ловушке (1 < n < 100 000).
В следующей строке через пробел перечислены n чисел ai — высоты ловушек (a[i]<1 000 000).
В третьей строке дано целое число k — количество раз, которое Том будет менять высоты платформ (1 < k < 100 000). В последней строке ввода даны k чисел xi, где xi — величина, на которую Том изменяет высоты платформ i-м действием (|xi| < 1 000 000).

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

После каждого действия Тома, выведите на новой строке суммарную опасность ловушки.
Примеры
стандартный ввод
3
2 3 1
3
-1 -2 4
стандартный вывод
3
3
9

0

Gger, в чем затык? Простая задача же.

0

iSmokeJC, я тупой просто

0

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

0

Сообщение от genrichg нужен другой способ

какой способ? какие идеи у вас?

0

Оставлю это здесь, может кому понадобится при подготовке к олимпиадам.

1) Сортируем массив а
2) Заполняем массив p префикс сумм.
3) В цикле когда идет ввод массива x.
3.1) накапливаем в переменную s += xi.
3.2) бинпоиском находим позицию в массива a, где ai+s < 0
3.3) вычисляем результат через массив префикс сумм p

итого сложность O(n*log(n)) + O(k*log(n))

0