Problem Description

On a 2D plane, there is a flying squirrel and $N$ pillars.

We represent a point on the 2D plane as $(x,y)$, where the $x$-coordinate represents the offset to the right, and the $y$-coordinate represents the offset upward.

The pillars are numbered $0 \sim N-1$ in order. The bottom of pillar $i$ is at $(i,0)$, and its height is infinite. In other words, pillar $i$ is a ray starting from $(i,0)$ and pointing upward. Each pillar is either red or blue. If $B[i]=0$, pillar $i$ is red; otherwise if $B[i]=1$, pillar $i$ is blue.

In the region outside the pillars, the squirrel flies horizontally to the right, keeping its current height unchanged. Since the squirrel is very agile, the time spent flying to the right is considered $0$.

When the squirrel is at a pillar, it can increase its height by $1$, or do nothing. More precisely, at pillar $i$, the squirrel must perform exactly one of the following operations:

• Pass through the pillar. The squirrel’s height does not change, and it continues flying to the right. The time cost is $0$.
• Climb up the pillar. This operation can be performed if and only if the pillar is red ($B[i]=0$). The squirrel’s height increases by $1$, then it continues flying to the right. The time cost is $A[i]$.
• Jump up the pillar. This operation can be performed if and only if the pillar is blue ($B[i]=1$). The squirrel’s height increases by $1$, then it continues flying to the right. The time cost is $A[i]$.

In addition, when the squirrel’s $x$-coordinate is $i+0.5$ ($0\le i\le N-1$), its height must be within $[L[i],R[i]]$. When the squirrel’s $x$-coordinate is $N$, its height must be $H$.

Let $T[k]$ be the minimum time needed for the squirrel to reach $(N,H)$ while satisfying all the conditions above and using exactly $k$ “Jump up” operations. If no such plan exists, let $T[k]=-1$.

Compute $T[0],T[1],\cdots,T[H]$.

Implementation Details

This is a functional interactive problem. You do not need to, and should not, implement the main function.

You should implement the following function:

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

• $H$: the squirrel’s final height.
• $A,B,L,R$: integer arrays of length $N$.
• $B$: the array describing pillar colors. If $B[i]=0$, pillar $i$ is red; otherwise if $B[i]=1$, pillar $i$ is blue.
• This function must return an array $T$ of length $(H+1)$.
• This function is called exactly once.

Your source code should not call any input/output functions.

Input Format

The input format of the sample grader is as follows:

• Line $1$: $N$ $H$
• Line $2$: $A[0]$ $A[1]$ $\ldots$ $A[N - 1]$
• Line $3$: $B[0]$ $B[1]$ $\ldots$ $B[N - 1]$
• Line $4$: $L[0]$ $L[1]$ $\ldots$ $L[N - 1]$
• Line $5$: $R[0]$ $R[1]$ $\ldots$ $R[N - 1]$

Output Format

The sample grader prints the answer in the following format:

• Line $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

Hint

Constraints

• $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$。

Subtasks

Samples

Sample $1$

Consider the following call.

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

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

If the squirrel jumps up pillar $0$ and climbs up pillars $1$ and $3$, then the conditions are satisfied. In this case, the number of “Jump up” operations is $1$, and the time cost is $20$ seconds.

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

If the squirrel jumps up pillars $0$ and $2$ and climbs up pillar $3$, then the conditions are satisfied. In this case, the number of “Jump up” operations is $2$, and the time cost is $14$ seconds.

There are no other possible ways. Therefore, the function should return [$-1$, $20$, $14$, $-1$].

Sample $2$

Consider the following call.

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

The function should return $[1000000000, -1]$.

Sample $3$

Consider the following call.

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

The function should return $[7, -1, -1, -1]$.

Sample $4$

Consider the following call.

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

The function should return $[-1, 16, 11, 10, 9, 10, 12, 15]$。

Translated by ChatGPT 5