A16452. Jumping Through Segments
编程题
普及/提高-
知识点
题目描述
Polycarp is designing a level for a game. The level consists of $n$ segments on the number line, where the $i$ -th segment starts at the point with coordinate $l_i$ and ends at the point with coordinate $r_i$ .
The player starts the level at the point with coordinate $0$ . In one move, they can move to any point that is within a distance of no more than $k$ . After their $i$ -th move, the player must land within the $i$ -th segment, that is, at a coordinate $x$ such that $l_i \le x \le r_i$ . This means:
- After the first move, they must be inside the first segment (from $l_1$ to $r_1$ );
- After the second move, they must be inside the second segment (from $l_2$ to $r_2$ );
- ...
- After the $n$ -th move, they must be inside the $n$ -th segment (from $l_n$ to $r_n$ ).
The level is considered completed if the player reaches the $n$ -th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of $k$ .
Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer $k$ with which it is possible to complete the level.
The player starts the level at the point with coordinate $0$ . In one move, they can move to any point that is within a distance of no more than $k$ . After their $i$ -th move, the player must land within the $i$ -th segment, that is, at a coordinate $x$ such that $l_i \le x \le r_i$ . This means:
- After the first move, they must be inside the first segment (from $l_1$ to $r_1$ );
- After the second move, they must be inside the second segment (from $l_2$ to $r_2$ );
- ...
- After the $n$ -th move, they must be inside the $n$ -th segment (from $l_n$ to $r_n$ ).
The level is considered completed if the player reaches the $n$ -th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of $k$ .
Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer $k$ with which it is possible to complete the level.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 10^4$ )—the number of test cases. Descriptions of the test cases follow.
The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ )—the number of segments in the level.
The following $n$ lines.
The $i$ -th line contain two integers $l_i$ and $r_i$ ( $0 \le l_i \le r_i \le 10^9$ )—the boundaries of the $i$ -th segment. Segments may intersect.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ )—the number of segments in the level.
The following $n$ lines.
The $i$ -th line contain two integers $l_i$ and $r_i$ ( $0 \le l_i \le r_i \le 10^9$ )—the boundaries of the $i$ -th segment. Segments may intersect.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, output a single integer—the minimum value of $k$ with which it is possible to complete the level.
输入输出样例
输入 #1
4 5 1 5 3 4 5 6 8 10 0 1 3 0 2 0 1 0 3 3 3 8 10 18 6 11 4 10 20 0 5 15 17 2 2
输出 #1
7 0 5 13
说明/提示
In the third example, the player can make the following moves:
- Move from point $0$ to point $5$ ( $3 \le 5 \le 8$ );
- Move from point $5$ to point $10$ ( $10 \le 10 \le 18$ );
- Move from point $10$ to point $7$ ( $6 \le 7 \le 11$ ).
Note that for the last move, the player could have chosen not to move and still complete the level.
- Move from point $0$ to point $5$ ( $3 \le 5 \le 8$ );
- Move from point $5$ to point $10$ ( $10 \le 10 \le 18$ );
- Move from point $10$ to point $7$ ( $6 \le 7 \le 11$ ).
Note that for the last move, the player could have chosen not to move and still complete the level.