A16387 | Wine Factory (Easy Version)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
This is the easy version of the problem. The only difference between the two versions is the constraint on $c_i$ and $z$ . You can make hacks only if both versions of the problem are solved.
There are three arrays $a$ , $b$ and $c$ . $a$ and $b$ have length $n$ and $c$ has length $n-1$ . Let $W(a,b,c)$ denote the liters of wine created from the following process.
Create $n$ water towers. The $i$ -th water tower initially has $a_i$ liters of water and has a wizard with power $b_i$ in front of it. Furthermore, for each $1 \le i \le n - 1$ , there is a valve connecting water tower $i$ to $i + 1$ with capacity $c_i$ .
For each $i$ from $1$ to $n$ in this order, the following happens:
1. The wizard in front of water tower $i$ removes at most $b_i$ liters of water from the tower and turns the removed water into wine.
2. If $i \neq n$ , at most $c_i$ liters of the remaining water left in water tower $i$ flows through the valve into water tower $i + 1$ .
There are $q$ updates. In each update, you will be given integers $p$ , $x$ , $y$ and $z$ and you will update $a_p := x$ , $b_p := y$ and $c_p := z$ . After each update, find the value of $W(a,b,c)$ . Note that previous updates to arrays $a$ , $b$ and $c$ persist throughout future updates.
There are three arrays $a$ , $b$ and $c$ . $a$ and $b$ have length $n$ and $c$ has length $n-1$ . Let $W(a,b,c)$ denote the liters of wine created from the following process.
Create $n$ water towers. The $i$ -th water tower initially has $a_i$ liters of water and has a wizard with power $b_i$ in front of it. Furthermore, for each $1 \le i \le n - 1$ , there is a valve connecting water tower $i$ to $i + 1$ with capacity $c_i$ .
For each $i$ from $1$ to $n$ in this order, the following happens:
1. The wizard in front of water tower $i$ removes at most $b_i$ liters of water from the tower and turns the removed water into wine.
2. If $i \neq n$ , at most $c_i$ liters of the remaining water left in water tower $i$ flows through the valve into water tower $i + 1$ .
There are $q$ updates. In each update, you will be given integers $p$ , $x$ , $y$ and $z$ and you will update $a_p := x$ , $b_p := y$ and $c_p := z$ . After each update, find the value of $W(a,b,c)$ . Note that previous updates to arrays $a$ , $b$ and $c$ persist throughout future updates.
输入格式
The first line contains two integers $n$ and $q$ ( $2 \le n \le 5\cdot 10^5$ , $1 \le q \le 5\cdot 10^5$ ) — the number of water towers and the number of updates.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the number of liters of water in water tower $i$ .
The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ( $0 \le b_i \le 10^9$ ) — the power of the wizard in front of water tower $i$ .
The fourth line contains $n - 1$ integers $c_1, c_2, \ldots, c_{n - 1}$ ( $c_i \color{red}{=} 10^{18}$ ) — the capacity of the pipe connecting water tower $i$ to $i + 1$ .
Each of the next $q$ lines contains four integers $p$ , $x$ , $y$ and $z$ ( $1 \le p \le n$ , $0 \le x, y \le 10^9$ , $z \color{red}{=} 10^{18}$ ) — the updates done to arrays $a$ , $b$ and $c$ .
Note that $c_n$ does not exist, so the value of $z$ does not matter when $p = n$ .
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the number of liters of water in water tower $i$ .
The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ( $0 \le b_i \le 10^9$ ) — the power of the wizard in front of water tower $i$ .
The fourth line contains $n - 1$ integers $c_1, c_2, \ldots, c_{n - 1}$ ( $c_i \color{red}{=} 10^{18}$ ) — the capacity of the pipe connecting water tower $i$ to $i + 1$ .
Each of the next $q$ lines contains four integers $p$ , $x$ , $y$ and $z$ ( $1 \le p \le n$ , $0 \le x, y \le 10^9$ , $z \color{red}{=} 10^{18}$ ) — the updates done to arrays $a$ , $b$ and $c$ .
Note that $c_n$ does not exist, so the value of $z$ does not matter when $p = n$ .
输出格式
Print $q$ lines, each line containing a single integer representing $W(a, b, c)$ after each update.
输入输出样例
输入 #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
输出 #1
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
输出 #2
34 25 29 21 27
The first update does not make any modifications to the arrays.
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $5$ liters of water in tower 2 and $4$ liters of water is turned into wine. The remaining $1$ liter of water flows into tower 3.
- When $i = 3$ , there are $4$ liters of water in tower 3 and $2$ liters of water is turned into wine. The remaining $2$ liters of water flows into tower 4.
- When $i = 4$ , there are $5$ liters of water in tower 4. All $5$ liters of water are turned into wine.
Hence, $W(a,b,c)=1 + 4 + 2 + 5 = 12$ after the first update.
The second update modifies the arrays to $a = [3, 5, 3, 3]$ , $b = [1, 1, 2, 8]$ , and $c = [10^{18}, 10^{18}, 10^{18}]$ .
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. The remaining $6$ liters of water flow into tower 3.
- When $i = 3$ , there are $9$ liters of water in tower 3 and $2$ liters of water is turned into wine. The remaining $7$ liters of water flow into tower 4.
- When $i = 4$ , there are $10$ liters of water in tower 4. Only $8$ liters of water is turned into wine.
Hence, $W(a,b,c)=1 + 1 + 2 + 8 = 12$ after the second update.
The third update modifies the arrays to $a = [3, 5, 0, 3]$ , $b = [1, 1, 0, 8]$ , and $c = [10^{18}, 10^{18}, 10^{18}]$ .
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. The remaining $6$ liters of water flow into tower 3.
- When $i = 3$ , there are $6$ liters of water in tower 3 and $0$ liters of water is turned into wine. The remaining $6$ liters of water flow into tower 4.
- When $i = 4$ , there are $9$ liters of water in tower 4. Only $8$ liters of water is turned into wine.
Hence, $W(a,b,c)=1 + 1 + 0 + 8 = 10$ after the third update.
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $5$ liters of water in tower 2 and $4$ liters of water is turned into wine. The remaining $1$ liter of water flows into tower 3.
- When $i = 3$ , there are $4$ liters of water in tower 3 and $2$ liters of water is turned into wine. The remaining $2$ liters of water flows into tower 4.
- When $i = 4$ , there are $5$ liters of water in tower 4. All $5$ liters of water are turned into wine.
Hence, $W(a,b,c)=1 + 4 + 2 + 5 = 12$ after the first update.
The second update modifies the arrays to $a = [3, 5, 3, 3]$ , $b = [1, 1, 2, 8]$ , and $c = [10^{18}, 10^{18}, 10^{18}]$ .
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. The remaining $6$ liters of water flow into tower 3.
- When $i = 3$ , there are $9$ liters of water in tower 3 and $2$ liters of water is turned into wine. The remaining $7$ liters of water flow into tower 4.
- When $i = 4$ , there are $10$ liters of water in tower 4. Only $8$ liters of water is turned into wine.
Hence, $W(a,b,c)=1 + 1 + 2 + 8 = 12$ after the second update.
The third update modifies the arrays to $a = [3, 5, 0, 3]$ , $b = [1, 1, 0, 8]$ , and $c = [10^{18}, 10^{18}, 10^{18}]$ .
- When $i = 1$ , there are $3$ liters of water in tower 1 and $1$ liter of water is turned into wine. The remaining $2$ liters of water flow into tower 2.
- When $i = 2$ , there are $7$ liters of water in tower 2 and $1$ liter of water is turned into wine. The remaining $6$ liters of water flow into tower 3.
- When $i = 3$ , there are $6$ liters of water in tower 3 and $0$ liters of water is turned into wine. The remaining $6$ liters of water flow into tower 4.
- When $i = 4$ , there are $9$ liters of water in tower 4. Only $8$ liters of water is turned into wine.
Hence, $W(a,b,c)=1 + 1 + 0 + 8 = 10$ after the third update.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted