codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.