#384. E - 货物集中作业
E - 货物集中作业
E - 货物集中作业
题目描述
有 座仓库从西向东排成一条直线,从西往东依次编号为 ,相邻两座仓库之间的距离为 。
初始时,仓库 中有 件货物。
高桥和青木依次进行 次货物集中作业。第 次作业指定一个闭区间 :高桥的卡车停在仓库 ,青木的卡车停在仓库 。
在这次作业中,作业开始时位于区间 内每座仓库的全部货物,都要被搬运到两个端点仓库中距离它更近的那个。如果到两个端点的距离相同,就搬运到左端点 。
搬运一件货物、距离为 的花费是 。
货物会真实地移动到目标仓库,因此后续操作基于更新后的货物分布。当前指定区间外的货物不会移动。
对于每次作业,依次输出该次作业的总搬运花费。
输入格式
第一行输入两个整数 。
第二行输入 个整数 。
接下来 行,每行输入两个整数 。
输出格式
输出 行,第 行输出第 次作业产生的总搬运花费。
注意:花费可能超过 32 位整数范围,需要使用 64 位整数。
数据范围
- 所有输入均为整数。
样例输入 1
5 3
2 0 3 1 4
1 3
2 5
1 5
样例输出 1
0
4
3
样例输入 2
5 4
0 5 2 5 0
1 5
2 4
1 2
4 5
样例输出 2
14
0
0
0
样例输入 3
12 8
10 0 5 3 8 2 0 7 1 4 6 9
1 6
4 12
2 9
5 6
1 12
7 11
3 10
6 8
样例输出 3
24
71
40
0
20
0
0
0
样例输入 4
30 20
5 0 12 7 100 3 8 15 0 21 4 9 30 2 17 6 11 0 25 14 1 18 7 33 0 10 5 28 13 19
1 30
5 20
10 25
2 3
14 18
7 29
1 15
16 30
8 9
12 27
3 22
20 21
4 30
1 2
9 17
6 24
11 13
15 28
2 19
23 30
样例输出 4
2731
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
样例输入 5
2 1
0 1000000
1 2
样例输出 5
0