eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ежедневное деление

Ежедневное деление

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Оостенде - очень длинный пляж, расположенный на севере Бельгии. На этом пляже находятся n хижин, расположенных вдоль прямой линии. Люди могут снять комнату в одной из этих хижин, чтобы провести отпуск на пляже вместе с другими жильцами.

Каждый день во время обеда едет грузовик с едой, чтобы подать картофель фри гостям. Грузовик припаркуется перед одной из хижин, и люди сформируют две очереди. Люди, находящиеся в хижинах слева от продовольственного грузовика, будут стоять в очереди слева, а люди справа от продовольственного грузовика будут стоять в очереди справа. Люди, стоящие в хижине перед грузовиком с едой, разделят свою группу пополам: одна половина пойдет в левую очередь, а другая половина - в правую. Если это нечетное количество людей, оставшийся человек пойдет в очередь с меньшим количеством людей, или выберет очередь случайным образом, если они имеют одинаковую длину. Грузовик с едой всегда будет располагаться так, чтобы разница между количеством людей в левой очереди и количеством людей в правой очереди была как можно меньше.

Каждую ночь количество гостей в одной из хижин меняется. Можете ли Вы помочь фургону найти лучшую позицию на каждый день?

Giriş verilənləri

Первая строка содержит два целых числа n (1n10^5) - количество хижин и q (1q10^5) - количество дней. Вторая строка содержит n целых чисел a[0], ..., a[n−1] удовлетворяющих 1a[i]10^6 for 0i < n, где a[i] - число людей в хижине i. Далее следуют q строк с двумя целыми числами i (0i < n) и x (1x10^6). j-ая строка указывает что в день j количество людей в хижине i изменяется на x.

Çıxış verilənləri

Выведите q строк - оптимальное положение грузовика после каждой q-ой ночи. Если существует несколько оптимальных позиций, выведите наименьшую.

Nümunə

Giriş verilənləri #1
5 4
3 1 3 4 2
0 5
0 9
4 5
2 1
Çıxış verilənləri #1
2
1
2
1
Giriş verilənləri #2
4 8
1 1 1 1
2 2
1 2
2 1
1 1
3 2
2 2
1 2
2 1
Çıxış verilənləri #2
1
1
1
1
1
2
2
2
Mənbə 2018 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Задача D