問題一覧 > 通常問題

No.2242 Cities and Teleporters

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 74
作問者 : shobonvipshobonvip / テスター : noya2noya2 👑 NachiaNachia
4 ProblemId : 9044 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 21:56:48

注意

入出力が多くなる場合があるので、高速な方法で入出力を行うことをおすすめします。

問題文

しょぼん国には NN 個の町があり、町は町 11、町 22\cdots、町 NN と番号付けられています。i=1,2,,Ni=1,2,\cdots, N について、町 ii の標高は HiH_i です。

しょぼん国は山地が多く不便なので、国王であるしょぼん君は全ての街に、それぞれの街から別の街に行けるテレポーターを設置しました。各 i=1,2,,Ni=1,2,\cdots, N について、町 ii のテレポーターを使うと、町 ii から標高が TiT_i 以下の別の任意の町に行くことができます。

QQ 個のクエリが与えられます。kk 番目のクエリでは、整数 Ak,BkA_k, B_k が与えられるので、町 AkA_k から町 BkB_k にテレポーターを経由して行くときのテレポーターの使用回数の最小値を出力してください。ただし、町 AkA_k から町 BkB_k にテレポーターを経由して行くことができない場合は、-1 を出力してください。

制約

  • 入力はすべて整数
  • 2N2×1052 \le N \le 2\times 10^5
  • 1Q2×1051 \le Q \le 2\times 10^5
  • 1Hi,Ti1091 \le H_i, T_i \le 10^9 (1iN)(1 \le i \le N)
  • 1Ak,BkN1 \le A_k, B_k \le N (1kQ)(1 \le k \le Q)
  • AkBkA_k \ne B_k

入力

NN
H1H_1 H2H_2 \cdots HNH_N
T1T_1 T2T_2 \cdots TNT_N
QQ
A1A_1 B1B_1
A2A_2 B2B_2
\vdots
AQA_Q BQB_Q

出力

QQ 行出力してください。kk (1kQ)(1\le k \le Q) 行目には、kk 番目のクエリの答えを出力してください。

サンプル

サンプル1
入力
4
1 7 2 9
6 1 7 3
4
1 3
1 2
2 3
2 4
出力
1
2
2
-1

22 番目のクエリにおいて、町 11 から町 22 にテレポーターで行くとき、テレポーターの使用回数の最小値は 22 なので、22 を出力します。
11 からは 標高が 66 以下の町に行くことが出来ますが、町 22 の標高は 77 であるので、11 回の移動で町 11 から町 22 に行くことは出来ません。よって、町 11 から町 22 に到達できるなら、22 回以上移動することが必要です。実際、町 11 \to33 \to22 と移動できるため、最小の移動回数は 22 になります。

44 番目のクエリにおいては、町 22 から町 44 にテレポーターで到達することができないため、-1 を出力します。

サンプル2
入力
2
100000000 1
1 1
2
1 2
2 1
出力
1
-1

テレポーターは双方向的ではないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。