codeforces-scrape

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

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.