Problem Description

In an alternate universe, Vlad is stuck inside a futuristic version of the Poenari Fortress, now spanning $n$ floors, numbered $0$ through $n - 1$. From each floor $i$ ($0 \leq i \leq n - 1$), he can only go up, either by taking the stairs and paying $1$ drop of blood (this is the currency that vampires use to pay in Romania), or by turning into a bat and traversing the vents, for which he has to pay $2$ drops of blood. The stairs can take him up to $v[i]$ floors upwards, while the vents span up to $w[i]$ floors upwards, where $v$ and $w$ are two given arrays: $v = v[0], v[1], \ldots, v[n - 1]$ and $w = w[0], w[1], \ldots, w[n - 1]$.

Formally, from floor $i$ ($0 \leq i \leq n - 1$), Vlad can go:

• anywhere from floor $i + 1$ to floor $i + v[i]$ without exceeding $n - 1$, for a cost of $1$
• anywhere from floor $i + 1$ to floor $i + w[i]$ without exceeding $n - 1$, for a cost of $2$

Furthermore, his brothers Radu and Mircea proposed $m$ scenarios for Vlad, each one consisting of two floors $A$ and $B$ ($A \leq B$). Vlad has to answer their $m$ questions: what is the least amount of blood that he has to sacrifice to get from floor $A$ to floor $B$?

Implementation Details

You will have to implement the function solve:

std::vector<int> solve(std::vector<int> &v, std::vector<int> &w, std::vector<std::pair<int,int>> &queries);

• Receives the vectors $v$, the heights of the flights of stairs, and $w$, the heights of the vent systems, starting at each floor, both of them of size $n$.
• Also receives the queries, a vector of pairs of size $m$. Each pair contains $A$ and $B$ as described in the statement.
• Returns a vector of size $m$, consisting of the answers to the $m$ queries.

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

2
3
4

10
1 1 1 2 3 2 1 1 2 3 
2 4 1 4 1 4 1 3 2 3 
5
3 9
0 9
0 7
0 4
3 5

3
5
4
3
1

Hint

Sample Explanation 1

Consider the following call:

solve({2, 3, 1, 1, 1, 1, 2}, {3, 4, 1, 2, 1, 2, 2}, {{0, 4}, {0, 5}, {0, 6}})

Here we have $n = 7$ and $3$ queries, $v = [2, 3, 1, 1, 1, 1, 2]$ and $w = [3, 4, 1, 2, 1, 2, 2]$.

For the first query $(0, 4)$, Vlad has to make two $1$-cost jumps: $0$ to $1$ (even though he can jump to $2$, floor $1$ will then take him further), then $1$ to $4$. Total cost: $1 + 1 = 2$.

For the second query $(0, 5)$, there are $2$ optimal paths: $0$ to $1$ (cost $1$), $1$ to $4$ (cost $1$), $4$ to $5$ (cost $1$); the second path is $0$ to $1$ (cost $1$), $1$ to $5$ (cost $2$). Total cost: $1 + 1 + 1 = 1 + 2 = 3$.

For the third query $(0, 6)$, one example path of cost $4$ is $0$ to $1$ (cost $1$), $1$ to $5$ (cost $2$), $5$ to $6$ (cost $1$). Total cost: $1 + 2 + 1 = 4$.

So the vector that the function will return must be: $\{2, 3, 4\}$

Sample Explanation 2

Consider the following call:

solve({1, 1, 1, 2, 3, 2, 1, 1, 2, 3}, {2, 4, 1, 4, 1, 4, 1, 3, 2, 3}, {{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}})

These are the optimal paths for the queries:

• $(3, 9)$: $3$ to $5$ (cost $1$), $5$ to $9$ (cost $2$) $\Rightarrow$ total: $3$
• $(0, 9)$: $0$ to $1$ (cost $1$), $1$ to $5$ (cost $2$), $5$ to $9$ (cost $2$) $\Rightarrow$ total: $5$
• $(0, 7)$: $0$ to $1$ (cost $1$), $1$ to $5$ (cost $2$), $5$ to $7$ (cost $1$) $\Rightarrow$ total: $4$
• $(0, 4)$: $0$ to $1$ (cost $1$), $1$ to $4$ (cost $2$) $\Rightarrow$ total: $3$
• $(3, 5)$: $3$ to $5$ (cost $1$) $\Rightarrow$ total: $1$

So the vector that the function will return must be: $\{3, 5, 4, 3, 1\}$

Constraints

• $1 \leq n, m \leq 500000$
• $1 \leq v[i], w[i] \leq n$ for all $0 \leq i \leq n - 1$
• $0 \leq A \leq B \leq n - 1$ for all queries

Subtasks

1. (5 points) $1 \leq n \leq 300, 1 \leq m \leq 500000$
2. (7 points) $1 \leq n \leq 3000, 1 \leq m \leq 3000$
3. (11 points) $1 \leq n \leq 20000, 1 \leq m \leq 20000$
4. (44 points) $1 \leq n \leq 200000, 1 \leq m \leq 200000$
5. (8 points) $1 \leq n \leq 500000, 1 \leq m \leq 500000, v[i] \leq v[j]$ and $w[i] \leq w[j]$ for all $0 \leq i < j \leq n - 1$
6. (25 points) No further restrictions