2037D.md (3110B)
1 Source: https://codeforces.com/problemset/problem/2037/D 2 3 D. Sharky Surfing 4 5 time limit per test 6 7 3 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 Mualani loves surfing on her sharky surfboard! 22 23 Mualani's surf path can be modeled by a number line. She starts at position $1$, and the path ends at position $L$. When she is at position $x$ with a jump power of $k$, she can jump to any integer position in the interval $[x, x+k]$. Initially, her jump power is $1$. 24 25 However, her surf path isn't completely smooth. There are $n$ hurdles on her path. Each hurdle is represented by an interval $[l, r]$, meaning she cannot jump to any position in the interval $[l, r]$. 26 27 There are also $m$ power-ups at certain positions on the path. Power-up $i$ is located at position $x_i$ and has a value of $v_i$. When Mualani is at position $x_i$, she has the option to collect the power-up to increase her jump power by $v_i$. There may be multiple power-ups at the same position. When she is at a position with some power-ups, she may choose to take or ignore each individual power-up. No power-up is in the interval of any hurdle. 28 29 What is the minimum number of power-ups she must collect to reach position $L$ to finish the path? If it is not possible to finish the surf path, output $-1$. 30 31 Input 32 33 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 34 35 The first line of each test case contains three integers $n$, $m$, and $L$ ($1 \leq n, m \leq 2 \cdot 10^5, 3 \leq L \leq 10^9$) — the number of hurdles, the number of power-ups, and the position of the end. 36 37 The following $n$ lines contain two integers $l_i$ and $r_i$ ($2 \leq l_i \leq r_i \leq L-1$) — the bounds of the interval for the $i$'th hurdle. It is guaranteed that $r_i + 1 \lt l_{i+1}$ for all $1 \leq i \lt n$ (i.e. all hurdles are non-overlapping, sorted by increasing positions, and the end point of a previous hurdle is not consecutive with the start point of the next hurdle). 38 39 The following $m$ lines contain two integers $x_i$ and $v_i$ ($1 \leq x_i, v_i \leq L$) — the position and the value for the $i$'th power-up. There may be multiple power-ups with the same $x$. It is guaranteed that $x_i \leq x_{i+1}$ for all $1 \leq i \lt m$ (i.e. the power-ups are sorted by non-decreasing position) and no power-up is in the interval of any hurdle. 40 41 It is guaranteed the sum of $n$ and the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, output the minimum number of power-ups she must collect to reach position $L$. If it is not possible, output $-1$. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 2 5 50 55 56 7 14 57 58 30 40 59 60 2 2 61 62 3 1 63 64 3 5 65 66 18 2 67 68 22 32 69 70 4 3 50 71 72 4 6 73 74 15 18 75 76 20 26 77 78 34 38 79 80 1 2 81 82 8 2 83 84 10 2 85 86 1 4 17 87 88 10 14 89 90 1 6 91 92 1 2 93 94 1 2 95 96 16 9 97 98 1 2 10 99 100 5 9 101 102 2 3 103 104 2 2 105 ``` 106 107 Output 108 109 ``` 110 4 111 -1 112 1 113 2 114 ``` 115 116 Note 117 118 In the first test case, she can collect power-ups $1$, $2$, $3$, and $5$ to clear all hurdles. 119 120 In the second test case, she cannot jump over the first hurdle. 121 122 In the fourth test case, by collecting both power-ups, she can jump over the hurdle.