直线上的容量运输¶
预估时间限制：2.5 秒。内存限制：128 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(18\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。 该倍率为题解中应通过的补充程序保留至少两倍实测余量。
背景故事¶
走廊上的工作站陆续产出物品。各工作站储位有限，末端仓库容量无限。调度员想知道每个物品前缀的最小搬运距离。
(本故事由GPT-6重写)
形式化问题描述¶
数轴上从左到右有 \(n+1\) 个点，编号为 \(1,\ldots,n+1\) .点 \(i\) 与点 \(i+1\) 的距离为 \(d_i\) ，可以为零。前 \(n\) 个点的容量分别为 \(r_1,\ldots,r_n\) ，点 \(n+1\) 容量无限。
共有 \(m\) 个物品，第 \(j\) 个在点 \(p_j\) 产生。每个物品必须存放在某个点，允许原地存放；有限容量点存放的物品数不能超过其容量。每个物品的运输费用是产生点到存放点的距离。
对每个 \(j=1,\ldots,m\) ，求存放前 \(j\) 个物品的最小总费用。各前缀的方案互不影响：优化新的前缀时，可以重新安排此前全部物品的存放位置。
输入格式¶
第一行两个整数 \(n,m\) .第二行给出 \(r_1,\ldots,r_n\) ，第三行给出 \(d_1,\ldots,d_n\) ，第四行给出 \(p_1,\ldots,p_m\) .
输出格式¶
输出 \(m\) 行，第 \(j\) 行是前 \(j\) 个物品的最小总费用。
样例¶
样例 1¶
输入¶
9 5
1 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 2
3 5 7 2 9
输出¶
1
2
3
3
5
样例 2¶
输入¶
8 4
1 0 1 0 1 0 1 0
2 1 1 1 1 1 1 3
4 6 8 2
输出¶
1
2
3
5
样例 3¶
输入¶
2 3
0 1
0 5
1 2 1
输出¶
0
5
10
样例解释¶
样例一的最小费用依次为 \(1,2,3,3,5\) .样例二各前缀允许重新安排已有物品。样例三前两个点距离为零，但只有一个有限储位；每增加一个后续物品，都要多付一次距离为五的仓库运输。
数据范围与保证¶
\(1\le n,m\le100000\) ，\(0\le r_i\le100000\) .对于 \(i<n\) ，有 \(0\le d_i\le2\) ；最后一段满足 \(0\le d_n\le1000000\) .所有请求满足 \(1\le p_j\le n\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |