题目描述

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

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

柱子依次编号 $0\sim N-1$。柱子 $i$ 的底部位于 $(i,0)$，高度为无穷高。换言之，柱子 $i$ 是一条从 $(i,0)$ 出发，方向向上的射线。每根柱子要么是红色，要么是蓝色。若 $B[i]=0$，柱子 $i$ 是红色的；否则 $B[i]=1$，柱子 $i$ 是蓝色的。

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

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

• 穿过柱子。松鼠的高度不变，继续向右飞行。消耗时间为 $0$。
• 爬上柱子。当且仅当柱子是红色的（$B[i]=0$）时可以执行该操作。松鼠的高度增加 $1$，然后继续向右飞行。消耗时间为 $A[i]$。
• 跳下柱子。当且仅当柱子是蓝色的（$B[i]=1$）时可以执行该操作。松鼠的高度减少 $1$，然后继续向右飞行。消耗时间为 $A[i]$。

此外，当松鼠横坐标为 $i+0.5$（$0\le i\le N-1$）时，松鼠的高度必须在 $[L[i],R[i]]$ 间。当松鼠横坐标为 $N$ 时，松鼠的高度必须为 $H$。

令 $T[k]$ 为满足上述条件的情况下，松鼠用恰好 $k$ 次「跳下」操作到达 $(N,H)$ 所花费的时间最小值。若不存在这样的方案，令 $T[k]=-1$。

求出 $T[0],T[1],\cdots,T[H]$。

实现细节

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

你应当实现以下的函数：

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$ 行：$N$ $H$
• 第 $2$ 行：$A[0]$ $A[1]$ $\ldots$ $A[N - 1]$
• 第 $3$ 行：$B[0]$ $B[1]$ $\ldots$ $B[N - 1]$
• 第 $4$ 行：$L[0]$ $L[1]$ $\ldots$ $L[N - 1]$
• 第 $5$ 行：$R[0]$ $R[1]$ $\ldots$ $R[N - 1]$

输出格式

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

• 第 $1$ 行：$T[0]$ $T[1]$ $\ldots$ $T[H]$

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

-1 20 14 -1

1 1
1000000000
0
1
1

1000000000 -1

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

7 -1 -1 -1

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

-1 16 11 10 9 10 12 15

提示

数据范围

• $1\le N\le 200\, 000$；
• $0\le H\le N$；
• $0\le A[i]\le 10^9$；
• $0\le B[i]\le 1$；
• $0\le L[i]\le R[i] \le N$。

子任务

编号	得分	限制
$1$	$3$	$N\le 300$
$2$	$4$	$A[i]=B[i]=0$
$3$	$25$	$B[i]=0$
$4$	$20$	$N\le 65\, 000, A[i]\le 5$
$5$	$29$	$N\le 65\, 000$
$6$	$19$	无额外限制

样例

样例 $1$

考虑以下调用。

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

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

如果松鼠从柱子 $0$ 跳下并爬上柱子 $1$ 和 $3$，则满足条件。在这种情况下，跳跃次数为 $1$，耗时为 $20$ 秒。

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

如果松鼠从柱子 $0$ 和 $2$ 跳下并爬上柱子 $3$，则满足条件。在这种情况下，跳跃次数为 $2$，耗时为 $14$ 秒。

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

样例 $2$

考虑以下调用。

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

函数应返回 $[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])

函数应返回 $[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]$。