問題一覧 > 通常問題

No.3072 Speedrun Query

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 : 👑 AngrySadEight / テスター : 遭難者 hamamu
3 ProblemId : 11894 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-15 18:11:31

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。