← 返回题目列表

Codeforces · 2023/F

F. 山丘和坑

中文机器翻译题面 查看原题

在一座丘陵地貌的沙漠城市,市政府决定购买一辆自卸车来平整路面。道路分为 $$$n$$$ 段,从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 部分的表面高度等于 $$$a_i$$$。如果第$$$i$$$路段的高度大于$$$0$$$,则自卸车必须从第$$$i$$$路段取沙,如果第$$$i$$$路段的高度小于$$$0$$$,则自卸车必须用沙子填充第$$$i$$$路段的坑。保证初始高度不等于$$$0$$$。

当自卸车处于第 $$$i$$$ 路段时,它可以带走 $$$x$$$ 单位的沙子,此时第 $$$i$$$ 路段的路面高度将减少 $$$x$$$,或者填充 $$$x$$$ 单位的沙子(前提是其当前路段中至少有 $$$x$$$ 单位的沙子)床),在这种情况下,第 $$$i$$$ 路段的路面高度将增加 $$$x$$$。

自卸车可以从任何路段开始行驶。移动到左侧或右侧的相邻部分需要$$$1$$$分钟,装卸沙子的时间可以忽略不计。自卸车的容量无限大,最初是空的。

您需要找到自卸车平整沙子所需的最短时间,以使每个部分的高度等于 $$$0$$$。请注意,在完成所有移动后,自卸车的车床上可能仍留有沙子。您需要针对编号从 $$$l_i$$$ 到 $$$r_i$$$ 的段独立解决此问题。不能使用段外的沙子。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — 节数和查询数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \neq 0$$$) — 每个部分的初始高度。

以下 $$$q$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 需要确定最短时间的段的边界。

保证所有测试用例的 $$$n$$$ 之和以及所有测试用例的 $$$q$$$ 之和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个查询,输出平整 $$$[l_i, r_i]$$$ 段中的沙子所需的最短时间,如果不可能,则输出 $$$-1$$$。

示例

输入 #1

5
1 1
-179
1 1
5 3
-2 2 -1 3 -1
2 4
1 5
1 3
7 1
1 1 1 -4 1 1 1
1 7
7 2
2 -2 2 -2 1 2 -1
1 7
2 7
4 4
1000000000 1000000000 999999999 -1000000000
2 4
3 4
2 3
1 3

输出 #1

-1
2
5
-1
8
6
6
2
-1
1
2

注意

在第一个测试用例中,需要将 $$$179$$$ 单位的沙子添加到唯一的部分。然而,无处可取,所以这是不可能的。

在第二个测试用例中:

- 在第一个查询中,自卸车可以在第二个路段开始行驶。它可以容纳 $$$2$$$ 单位的沙子,之后第二部分的高度将变为 $$$0$$$。然后自卸车就可以移动到第三段。它可以在那里倒$$$1$$$单位的沙子,之后第三部分的高度将变成$$$0$$$。然后自卸车就可以移动到第四节段。在那里它可以容纳 $$$3$$$ 单位的沙子,之后第四部分的高度将变为 $$$0$$$。总共,自卸车的移动时间为 $$$2$$$ 分钟。
- 在第二个查询中,自卸车可以在第四个路段开始行驶。它可以容纳 $$$3$$$ 单位的沙子,之后第四部分的高度将变为 $$$0$$$。然后自卸车就可以移动到第五节段。它可以在那里倒$$$1$$$单位的沙子,之后第五部分的高度将变成$$$0$$$。然后自卸车可以移回第四段,然后再移至第三段。它可以在那里倒$$$1$$$单位的沙子,之后第三部分的高度将变成$$$0$$$。然后自卸车就可以移动到第二段。它可以使用 $$$2$$$ 单位的沙子。然后它可以移动到第一部分。它可以在那里倒$$$2$$$单位的沙子,之后第一部分的高度将变成$$$0$$$。总共,自卸车将花费 $$$5$$$ 分钟的移动时间。
- 在第三个查询中,自卸车将无法使每个部分的高度等于$$$0$$$。