No.2242 Cities and Teleporters
Note
The input and output may be large, so we recommend using fast I/O methods.
Problem Statement
The Country of Shobon has $N$ towns, numbered town $1$, town $2$, $\cdots$, town $N$. For $i=1,2,\cdots, N$, the elevation of town $i$ is $H_i$.
Since the Country of Shobon is mountainous and inconvenient to travel in, its king, Shobon-kun, has installed in every town a teleporter that leads from that town to other towns. For each $i=1,2,\cdots, N$, using the teleporter of town $i$, one can go from town $i$ to any other town whose elevation is at most $T_i$.
You are given $Q$ queries. In the $k$-th query, integers $A_k, B_k$ are given. Output the minimum number of teleporter uses needed to go from town $A_k$ to town $B_k$ via teleporters. However, if it is impossible to go from town $A_k$ to town $B_k$ via teleporters, output -1.
Constraints
- All input values are integers.
- $2 \le N \le 2\times 10^5$
- $1 \le Q \le 2\times 10^5$
- $1 \le H_i, T_i \le 10^9$ $(1 \le i \le N)$
- $1 \le A_k, B_k \le N$ $(1 \le k \le Q)$
- $A_k \ne B_k$
Input
$N$ $H_1$ $H_2$ $\cdots$ $H_N$ $T_1$ $T_2$ $\cdots$ $T_N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_Q$ $B_Q$
Output
Output $Q$ lines. On the $k$-th line $(1\le k \le Q)$, output the answer to the $k$-th query.
Sample
Sample 1
Input
4 1 7 2 9 6 1 7 3 4 1 3 1 2 2 3 2 4
Output
1 2 2 -1
In the $2$-nd query, the minimum number of teleporter uses to go from town $1$ to town $2$ by teleporter is $2$, so output $2$.
From town $1$ one can go to towns with elevation at most $6$, but the elevation of town $2$ is $7$, so it is impossible to go from town $1$ to town $2$ in $1$ move. Therefore, reaching town $2$ from town $1$, if possible, requires at least $2$ moves. In fact, one can move as town $1 \to$ town $3 \to$ town $2$, so the minimum number of moves is $2$.
In the $4$-th query, town $4$ cannot be reached from town $2$ by teleporter, so output -1.
Sample 2
Input
2 100000000 1 1 1 2 1 2 2 1
Output
1 -1
Note that teleporters are not bidirectional.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia