AdditionalFile5624.zip

#5624. 「KTSC 2026 R2」飞鼠 2

标签: 传统 | 时间限制: 5000 ms | 内存限制: 2048 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "squirrel2.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T3 「날다람쥐 2」

在二维平面上有一只飞鼠和 $N$ 根柱子。

二维平面上的点可以用 $(x, y)$ 的形式表示。其中，$x$ 表示水平位置，$y$ 表示高度。水平位置 $x$ 增加的方向为右侧，高度 $y$ 增加的方向为上方。

柱子按顺序从 $0$ 号到 $N-1$ 号进行编号。第 $i$ $(0 \leq i \leq N-1)$ 号柱子的底部位于点 $(i, 0)$，其高度是无限的。因此，第 $i$ 号柱子是从点 $(i, 0)$ 开始向上延伸的射线。每根柱子要么是红色，要么是蓝色。如果 $B[i]=0$，则第 $i$ 号柱子是红色的；如果 $B[i]=1$，则第 $i$ 号柱子是蓝色的。

起初，飞鼠位于点 $(0, 0)$。它想要到达点 $(N, H)$。为此，飞鼠按以下方式移动：

在没有柱子的地方，飞鼠会保持当前高度向右飞行。由于飞鼠的速度极快，此时消耗的时间视为 $0$。

在有柱子的地方，飞鼠可以选择增加 $1$ 个单位的高度，也可以选择什么都不做。具体来说，在第 $i$ $(0 \leq i \leq N-1)$ 号柱子所在的位置，飞鼠必须执行以下动作之一：

• 穿过柱子：飞鼠的高度保持不变，继续向右飞行。消耗的时间为 $0$。
• 爬上柱子：该动作仅在柱子为红色时 $(B[i]=0)$ 可行。飞鼠在柱子处的高度增加 $1$，随后继续向右飞行。消耗的时间为 $A[i]$。
• 在柱子上跳跃：该动作仅在柱子为蓝色时 $(B[i]=1)$ 可行。飞鼠在柱子处的高度增加 $1$，随后继续向右飞行。消耗的时间为 $A[i]$。

此外，当飞鼠经过水平位置为 $i+0.5$ $(0 \leq i \leq N-1)$ 的点时，飞鼠的高度必须在 $[L[i], R[i]]$ 之间。当飞鼠到达水平位置为 $N$ 的点时，其高度必须恰好为 $H$。

在所有满足上述条件并到达 $(N, H)$ 的方法中，将飞鼠跳跃次数恰好为 $k$ 次时所消耗的总时间最小值定义为 $T[k]$。如果不存在这样的方法，则定义 $T[k]=-1$。 请计算 $T[0], T[1], \dots, T[H]$。

实现细节

你需要实现以下函数：

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

• $H$：飞鼠的最终高度。
• $A, B, L, R$：大小为 $N$ 的整数数组。
• $B$：表示柱子颜色的数组。如果 $B[i]=0$，第 $i$ 号柱子为红色；如果 $B[i]=1$，第 $i$ 号柱子为蓝色。
• 该函数应返回一个大小为 $H+1$ 的数组 $T$。
• 该函数仅会被调用一次。

样例 1

考虑如下调用：

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

如果在 $0$ 号柱子跳跃，并爬上 $1$ 号、 $3$ 号柱子，即可满足条件。在这种情况下，跳跃次数为 $1$ 次，耗时为 $20$ 秒。

如果在 $0$ 号、 $2$ 号柱子跳跃，并爬上 $3$ 号柱子，即可满足条件。在这种情况下，跳跃次数为 $2$ 次，耗时为 $14$ 秒。

不存在其他可行的方法。因此，函数应返回 $[-1, 20, 14, -1]$。

样例 2

考虑如下调用：

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

由于只有 $0$ 号柱子且为红色（只能爬），到达高度 $1$ 需耗时 $10^9$，跳跃次数为 $0$。因此函数应返回 $[1000000000, -1]$。

样例 3

考虑如下调用：

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])

所有柱子均为红色，因此跳跃次数只能为 $0$。函数应返回 $[7, -1, -1, -1]$。

样例 4

考虑如下调用：

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])

函数应返回 $[-1, 16, 11, 10, 9, 10, 12, 15]$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 200000$
• $0 \leq H \leq N$
• 对于所有 $i$，满足 $0 \leq A[i] \leq 10^{9}$ $(0 \leq i \leq N-1)$
• 对于所有 $i$，满足 $0 \leq B[i] \leq 1$ $(0 \leq i \leq N-1)$
• 对于所有 $i$，满足 $0 \leq L[i] \leq R[i] \leq N$ $(0 \leq i \leq N-1)$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$3$	$N \leq 300$
$2$	$4$	对于所有 $0 \leq i \leq N-1$，满足 $A[i]=B[i]=0$
$3$	$25$	对于所有 $0 \leq i \leq N-1$，满足 $B[i]=0$
$4$	$20$	$N \leq 65000$，且对于所有 $0 \leq i \leq N-1$，满足 $A[i] \leq 5$
$5$	$29$	$N \leq 65000$
$6$	$19$	无附加限制

示例评测程序

示例评测程序的输入格式如下：

• 第一行包含两个整数 $N$ 和 $H$。
• 第二行包含 $N$ 个整数 $A[0], A[1], \ldots, A[N-1]$。
• 第三行包含 $N$ 个整数 $B[0], B[1], \ldots, B[N-1]$。
• 第四行包含 $N$ 个整数 $L[0], L[1], \ldots, L[N-1]$。
• 第五行包含 $N$ 个整数 $R[0], R[1], \ldots, R[N-1]$。

示例评测程序按以下格式输出答案：

• 第一行输出 $H+1$ 个整数 $T[0], T[1], \ldots, T[H]$。