#215620. [KTSC 2026] 飞扬的松鼠 2 / Flying Squirrel 2

在二维平面上有一只飞扬的松鼠和 根柱子。

我们将二维平面上的点表示为 ，其中横坐标 代表向右的偏移，纵坐标 代表向上的偏移。

柱子依次编号 。柱子 的底部位于 ，高度为无穷高。换言之，柱子 是一条从 出发，方向向上的射线。每根柱子要么是红色，要么是蓝色。若 ，柱子 是红色的；否则 ，柱子 是蓝色的。

在柱子以外的区域，松鼠向右水平飞行，维持现有高度不变。由于松鼠十分敏捷，向右飞行的时间视为 。

当松鼠在柱子上时，松鼠可以将自己的高度增加 ，或者什么都不做。准确地说，在柱子 的位置时，松鼠必须执行下列恰好一个操作：

• 穿过柱子。松鼠的高度不变，继续向右飞行。消耗时间为 。
• 爬上柱子。当且仅当柱子是红色的（）时可以执行该操作。松鼠的高度增加 ，然后继续向右飞行。消耗时间为 。
• 跳上柱子。当且仅当柱子是蓝色的（）时可以执行该操作。松鼠的高度增加 ，然后继续向右飞行。消耗时间为 。

此外，当松鼠横坐标为 （）时，松鼠的高度必须在 间。当松鼠横坐标为 时，松鼠的高度必须为 。

令 为满足上述条件的情况下，松鼠用恰好 次「跳上」操作到达 所花费的时间最小值。若不存在这样的方案，令 。

求出 。

实现细节

这是一道函数式交互题。你不必，也不应实现 main 函数。

你应当实现以下的函数：

vector<long long> fly(int H, vector<int> A, vector<int> B, vector<int> L, vector<int> R)

• ：松鼠的最终高度。
• ：大小为 的整数数组。
• ：描述柱子颜色的数组。若 ，柱子 是红色的；否则 ，柱子 是蓝色的。
• 该函数必须返回一个大小为 的数组 。
• 该函数被调用恰好一次。

你的源代码中不应调用任何输入/输出函数。

样例评分程序的输入格式如下：

• 第 行：
• 第 行：
• 第 行：
• 第 行：
• 第 行：

样例评分程序按以下格式打印答案：

• 第 行：

样例输入 1

4 3
8 8 2 4
1 0 1 0
1 0 2 3
1 2 2 4

样例输出 1

-1 20 14 -1

样例输入 2

1 1
1000000000
0
1
1

样例输出 2

1000000000 -1

样例输入 3

7 3
4 7 0 3 8 4 5
0 0 0 0 0 0 0
0 0 0 1 0 1 2
5 1 2 5 5 6 3

样例输出 3

7 -1 -1 -1

样例输入 4

20 7
3 3 4 1 3 2 0 1 4 3 4 0 0 1 0 4 4 5 5 0
1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1
0 0 1 1 2 1 2 2 1 1 0 1 1 3 2 2 1 6 4 4
3 2 3 3 6 2 2 4 3 4 4 5 3 6 6 5 7 8 8 9

样例输出 4

-1 16 11 10 9 10 12 15

数据范围

• ；
• ；
• ；
• ；
• 。

子任务

样例

样例

考虑以下调用。

fly(3, [8, 8, 2, 4],
    [1, 0, 1, 0],
    [1, 0, 2, 3],
    [1, 2, 2, 4])

::::align{center} ::::

如果松鼠跳上柱子 并爬上柱子 和 ，则满足条件。在这种情况下，「跳上」次数为 ，耗时为 秒。

::::align{center} ::::

如果松鼠从跳上柱子 和 并爬上柱子 ，则满足条件。在这种情况下，「跳上」次数为 ，耗时为 秒。

没有其他可能的方法。因此，函数应返回 [, , , ]。

样例

考虑以下调用。

fly(1, [1000000000],
    [0],
    [1],
    [1])

函数应返回 。

样例

考虑以下调用。

fly(3, [4, 7, 0, 3, 8, 4, 5],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 2],
    [5, 1, 2, 5, 5, 6, 3])

函数应返回 。

样例

考虑以下调用。

fly(7, [3, 3, 4, 1, 3, 2, 0, 1, 4, 3, 4, 0, 0, 1, 0, 4, 4, 5, 5, 0],
    [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1],
    [0, 0, 1, 1, 2, 1, 2, 2, 1, 1, 0, 1, 1, 3, 2, 2, 1, 6, 4, 4],
    [3, 2, 3, 3, 6, 2, 2, 4, 3, 4, 4, 5, 3, 6, 6, 5, 7, 8, 8, 9])

函数应返回 。