No.3072 Speedrun Query
タグ : / 解いたユーザー数 68
作問者 : 👑



問題文
$N$ 個の基地 $1, 2, \dots, N$ が,一直線上に並んでいます.$1 \leq i \leq N - 1$ を満たす整数 $i$ に対して,基地 $i$ と基地 $i + 1$ は相互に道で繋がっており,時間 $1$ で移動することができます.
また,$N$ 個の基地のうち $K_A$ 個にはタイプ A のワープゾーンが,$K_B$ 個にはタイプ B のワープゾーンがあります.
タイプ A のワープゾーンは,基地 $a_1, a_2, \dots, a_{K_A}$ に,タイプ B のワープゾーンは,基地 $b_1, b_2, \dots, b_{K_B}$ に置かれています.
今自身のいる基地にワープゾーンがあるとき,そのワープゾーンと同じ種類のワープゾーンのある基地に瞬時に移動することができます(すなわち時間 $0$ で移動できます).
$Q$ 個のクエリが与えられます.$i$ 番目のクエリでは整数 $s_i, t_i$ が与えられるので,それぞれについて答えてください.
- 基地 $s_i$ から基地 $t_i$ まで道およびワープゾーンをそれぞれ好きな回数($0$ 回でもよい)用いて移動するとき,かかる時間は最短でいくらか.
制約
- 入力は全て整数
- $2 \leq N \leq 3 \times 10^5$
- $2 \leq K_A, K_B \leq N$
- $1 \leq a_1 < \dots < a_{K_A} \leq N$
- $1 \leq b_1 < \dots < b_{K_B} \leq N$
- $1 \leq Q \leq 3 \times 10^5$
- $1 \leq s_i < t_i \leq N$
入力
入力は以下の形式で標準入力から与えられる.
$N$ $K_A$ $K_B$ $a_1$ $a_2$ $\dots$ $a_{K_A}$ $b_1$ $b_2$ $\dots$ $b_{K_B}$ $Q$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_Q$ $t_Q$
出力
$Q$ 行出力せよ.$i(1 \leq i \leq Q)$ 行目には,$i$ 番目のクエリの答えを出力せよ.
なお,入出力が大きくなる場合があるため,高速な方法で入出力を行うことを推奨する.
サンプル
サンプル1
入力
10 2 3 1 8 4 6 7 5 1 10 1 8 9 10 6 7 1 4
出力
2 0 1 0 1
$1$ つ目のクエリについて,タイプ A のワープゾーンの利用により,基地 $8$ まで移動し,その後基地 $10$ まで道を用いて移動することで,時間 $2$ で移動できます.時間 $1$ 以下で移動できる方法はありません.
$2$ つ目のクエリについて,タイプ A のワープゾーンのみを利用することにより,基地 $8$ まで移動できます.このときにかかる時間は $0$ です.
$3$ つ目のクエリについて,基地 $9$ から基地 $10$ までワープゾーンを用いずに道を用いて移動することにより,時間 $1$ で移動できます.時間 $0$ で移動できる方法はありません.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。