問題一覧 > 通常問題

No.2242 Cities and Teleporters

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 76
作問者 : shobonvip / テスター : noya2 👑 Nachia
お気に入りにしたユーザー ProblemId : 9044 / 自分の提出
問題文最終更新日: 2023-03-10 21:56:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 380 (順位表) の他の問題:

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