1907D.md (2502B)
1 Source: https://codeforces.com/problemset/problem/1907/D 2 3 D. Jumping Through Segments 4 5 time limit per test 6 7 5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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: 24 25 * After the first move, they must be inside the first segment (from $l_1$ to $r_1$); 26 * After the second move, they must be inside the second segment (from $l_2$ to $r_2$); 27 * ... 28 * After the $n$-th move, they must be inside the $n$-th segment (from $l_n$ to $r_n$). 29 30 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$. 31 32 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. 33 34 Input 35 36 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. 37 38 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. 39 40 The following $n$ lines. 41 42 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. 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 45 46 Output 47 48 For each test case, output a single integer—the minimum value of $k$ with which it is possible to complete the level. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 5 58 59 1 5 60 61 3 4 62 63 5 6 64 65 8 10 66 67 0 1 68 69 3 70 71 0 2 72 73 0 1 74 75 0 3 76 77 3 78 79 3 8 80 81 10 18 82 83 6 11 84 85 4 86 87 10 20 88 89 0 5 90 91 15 17 92 93 2 2 94 ``` 95 96 Output 97 98 ``` 99 7 100 0 101 5 102 13 103 ``` 104 105 Note 106 107 In the third example, the player can make the following moves: 108 109 * Move from point $0$ to point $5$ ($3 \le 5 \le 8$); 110 * Move from point $5$ to point $10$ ($10 \le 10 \le 18$); 111 * Move from point $10$ to point $7$ ($6 \le 7 \le 11$). 112 113 Note that for the last move, the player could have chosen not to move and still complete the level.