Hello 2024 |
---|
Закончено |
Это простая версия задачи. Единственное различие между двумя версиями заключается в ограничениях на $$$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$$$ в этом порядке происходит следующее:
Дано $$$q$$$ обновлений. В каждом обновлении вам будут даны целые числа $$$p$$$, $$$x$$$, $$$y$$$ и $$$z$$$, означающие следующие изменения: $$$a_p := x$$$, $$$b_p := y$$$ и $$$c_p := z$$$. После каждого обновления найдите значение $$$W(a,b,c)$$$. Обратите внимание, что предыдущие обновления массивов $$$a$$$, $$$b$$$ и $$$c$$$ сохраняются во всех последующих обновлениях.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 5\cdot 10^5$$$, $$$1 \le q \le 5\cdot 10^5$$$) — количество водонапорных башен и количество обновлений.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество литров воды в водонапорной башне $$$i$$$.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — сила волшебника перед водонапорной башней $$$i$$$.
Четвертая строка содержит $$$n - 1$$$ целых чисел $$$c_1, c_2, \ldots, c_{n - 1}$$$ ($$$c_i \color{red}{=} 10^{18}$$$) — пропускная способность трубы, соединяющей водонапорную башню $$$i$$$ с $$$i + 1$$$.
Каждая из следующих $$$q$$$ строк содержит четыре целых числа $$$p$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le p \le n$$$, $$$0 \le x, y \le 10^9$$$, $$$z \color{red}{=} 10^{18}$$$) — обновления массивов $$$a$$$, $$$b$$$ и $$$c$$$.
Заметим, что $$$c_n$$$ не существует, поэтому величина $$$z$$$ не имеет значения при $$$p = n$$$.
Выведите $$$q$$$ строк, каждая из которых содержит одно целое число, равняющееся $$$W(a, b, c)$$$ после каждого обновления.
4 33 3 3 31 4 2 81000000000000000000 1000000000000000000 10000000000000000004 3 8 10000000000000000002 5 1 10000000000000000003 0 0 1000000000000000000
12 12 10
5 510 3 8 9 23 4 10 8 11000000000000000000 1000000000000000000 1000000000000000000 10000000000000000005 4 9 10000000000000000001 1 1 10000000000000000002 7 4 10000000000000000004 1 1 10000000000000000001 8 3 1000000000000000000
34 25 29 21 27
Первое обновление не вносит никаких изменений в массивы.
Следовательно, $$$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}]$$$.
Следовательно, $$$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}]$$$.
Следовательно, $$$W(a,b,c)=1 + 1 + 0 + 8 = 10$$$ после третьего обновления.
Название |
---|