A15051. Antennas
编程题
普及/提高-
知识点
题目描述
There are $n$ equidistant antennas on a line, numbered from $1$ to $n$ . Each antenna has a power rating, the power of the $i$ -th antenna is $p_i$ .
The $i$ -th and the $j$ -th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $|i-j| \leq \min(p_i, p_j)$ . Sending a message directly between two such antennas takes $1$ second.
What is the minimum amount of time necessary to send a message from antenna $a$ to antenna $b$ , possibly using other antennas as relays?
The $i$ -th and the $j$ -th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $|i-j| \leq \min(p_i, p_j)$ . Sending a message directly between two such antennas takes $1$ second.
What is the minimum amount of time necessary to send a message from antenna $a$ to antenna $b$ , possibly using other antennas as relays?
输入格式
Each test contains multiple test cases. The first line contains an integer $t$ ( $1\le t\le 100\,000$ ) — the number of test cases. The descriptions of the $t$ test cases follow.
The first line of each test case contains three integers $n$ , $a$ , $b$ ( $1 \leq a, b \leq n \leq 200\,000$ ) — the number of antennas, and the origin and target antenna.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ( $1 \leq p_i \leq n$ ) — the powers of the antennas.
The sum of the values of $n$ over all test cases does not exceed $200\,000$ .
The first line of each test case contains three integers $n$ , $a$ , $b$ ( $1 \leq a, b \leq n \leq 200\,000$ ) — the number of antennas, and the origin and target antenna.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ( $1 \leq p_i \leq n$ ) — the powers of the antennas.
The sum of the values of $n$ over all test cases does not exceed $200\,000$ .
输出格式
For each test case, print the number of seconds needed to trasmit a message from $a$ to $b$ . It can be shown that under the problem constraints, it is always possible to send such a message.
输入输出样例
输入 #1
3 10 2 9 4 1 1 1 5 1 1 1 1 5 1 1 1 1 3 1 3 3 3 1
输出 #1
4 0 2
说明/提示
In the first test case, we must send a message from antenna $2$ to antenna $9$ . A sequence of communications requiring $4$ seconds, which is the minimum possible amount of time, is the following:
- In $1$ second we send the message from antenna $2$ to antenna $1$ . This is possible since $|2-1|\le \min(1, 4) = \min(p_2, p_1)$ .
- In $1$ second we send the message from antenna $1$ to antenna $5$ . This is possible since $|1-5|\le \min(4, 5) = \min(p_1, p_5)$ .
- In $1$ second we send the message from antenna $5$ to antenna $10$ . This is possible since $|5-10|\le \min(5, 5) = \min(p_5, p_{10})$ .
- In $1$ second we send the message from antenna $10$ to antenna $9$ . This is possible since $|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$ .
- In $1$ second we send the message from antenna $2$ to antenna $1$ . This is possible since $|2-1|\le \min(1, 4) = \min(p_2, p_1)$ .
- In $1$ second we send the message from antenna $1$ to antenna $5$ . This is possible since $|1-5|\le \min(4, 5) = \min(p_1, p_5)$ .
- In $1$ second we send the message from antenna $5$ to antenna $10$ . This is possible since $|5-10|\le \min(5, 5) = \min(p_5, p_{10})$ .
- In $1$ second we send the message from antenna $10$ to antenna $9$ . This is possible since $|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$ .