Это простая версия задачи. Единственное различие между двумя версиями заключается в ограничениях на \(c_i\) и \(z\). Вы можете делать взломы, только если обе версии задачи решены.
Даны три массива \(a\), \(b\) и \(c\). \(a\) и \(b\) имеют длину \(n\), а \(c\) — длину \(n-1\). Обозначим за \(W(a,b,c)\) количество литров вина, произведённых в результате следующего процесса.
Построим \(n\) водонапорных башен. Изначально \(i\)-я водонапорная башня имеет \(a_i\) литров воды, и перед ней стоит волшебник с силой \(b_i\). Кроме того, для каждого \(1 \le i \le n - 1\) существует клапан, соединяющий водонапорную башню \(i\) с \(i + 1\), и имеющий пропускную способность \(c_i\).
Для каждого \(i\) от \(1\) до \(n\) в этом порядке происходит следующее:
- Волшебник, стоящий перед водонапорной башней \(i\), забирает из башни не более \(b_i\) литров воды и превращает забранную воду в вино.
- Если \(i \neq n\), то не более \(c_i\) литров воды, оставшейся в водонапорной башне \(i\), вытекает через клапан в водонапорную башню \(i + 1\).
Дано \(q\) обновлений. В каждом обновлении вам будут даны целые числа \(p\), \(x\), \(y\) и \(z\), означающие следующие изменения: \(a_p := x\), \(b_p := y\) и \(c_p := z\). После каждого обновления найдите значение \(W(a,b,c)\). Обратите внимание, что предыдущие обновления массивов \(a\), \(b\) и \(c\) сохраняются во всех последующих обновлениях.
Выходные данные
Выведите \(q\) строк, каждая из которых содержит одно целое число, равняющееся \(W(a, b, c)\) после каждого обновления.
Примечание
Первое обновление не вносит никаких изменений в массивы.
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(5\) литров воды, и \(4\) литра воды превращается в вино. Оставшийся \(1\) литр воды попадает в башню 3.
- Для \(i = 3\), в башне 3 находится \(4\) литра воды, и \(2\) литра воды превращается в вино. Оставшиеся \(2\) литра воды попадают в башню 4.
- Для \(i = 4\), в башне 4 находится \(5\) литров воды. Все \(5\) литров воды превращаются в вино.
Следовательно, \(W(a,b,c)=1 + 4 + 2 + 5 = 12\) после первого обновления.
Второе обновление изменяет массивы на \(a = [3, 5, 3, 3]\), \(b = [1, 1, 2, 8]\) и \(c = [10^{18}, 10^{18}, 10^{18}]\).
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(7\) литров воды, и \(1\) литр воды превращается в вино. Оставшиеся \(6\) литров воды попадают в башню 3.
- Для \(i = 3\), в башне 3 находится \(9\) литров воды и \(2\) литра воды превращается в вино. Оставшиеся \(7\) литров воды попадают в башню 4.
- Для \(i = 4\), в башне 4 находится \(10\) литров воды. Только \(8\) литров воды превращается в вино.
Следовательно, \(W(a,b,c)=1 + 1 + 2 + 8 = 12\) после второго обновления.
Третье обновление изменяет массивы на \(a = [3, 5, 0, 3]\), \(b = [1, 1, 0, 8]\) и \(c = [10^{18}, 10^{18}, 10^{18}]\).
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(7\) литров воды, и \(1\) литр воды превращается в вино. Оставшиеся \(6\) литров воды попадают в башню 3.
- Для \(i = 3\), в башне 3 находится \(6\) литров воды, и \(0\) литров воды превращается в вино. Оставшиеся \(6\) литров воды попадают в башню 4.
- Для \(i = 4\), в башне 4 находится \(9\) литров воды. Только \(8\) литров воды превращается в вино.
Следовательно, \(W(a,b,c)=1 + 1 + 0 + 8 = 10\) после третьего обновления.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
3 3 3 3
1 4 2 8
1000000000000000000 1000000000000000000 1000000000000000000
4 3 8 1000000000000000000
2 5 1 1000000000000000000
3 0 0 1000000000000000000
|
12
12
10
|
|
2
|
5 5
10 3 8 9 2
3 4 10 8 1
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
5 4 9 1000000000000000000
1 1 1 1000000000000000000
2 7 4 1000000000000000000
4 1 1 1000000000000000000
1 8 3 1000000000000000000
|
34
25
29
21
27
|