codeforces-scrape

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

2126D.md (2066B)


      1 Source: https://codeforces.com/problemset/problem/2126/D
      2 
      3 D. This Is the Last Time
      4 
      5 time limit per test
      6 
      7 2 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 You are given $n$ casinos, numbered from $1$ to $n$. Each casino is described by three integers: $l_i$, $r_i$, and $real_i$ ($l_i \le real_i \le r_i$). You initially have $k$ coins.
     22 
     23 You can play at casino $i$ only if the current number of coins $x$ satisfies $l_i \le x \le r_i$. After playing, your number of coins becomes $real_i$.
     24 
     25 You can visit the casinos in any order and are not required to visit all of them. Each casino can be visited no more than once.
     26 
     27 Your task is to find the maximum final number of coins you can obtain.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $0 \le k \le 10^9$) — the number of casinos and the initial number of coins.
     34 
     35 This is followed by $n$ lines. In the $i$-th line, there are three integers $l_i$, $r_i$, $real_i$ ($0 \le l_i \le real_i \le r_i \le 10^9$) — the parameters of the $i$-th casino.
     36 
     37 It is guaranteed that the sum of all $n$ across all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the maximum number of coins you can obtain after optimally choosing the order of visiting the casinos.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 3 1
     51 
     52 2 3 3
     53 
     54 1 2 2
     55 
     56 3 10 10
     57 
     58 1 0
     59 
     60 1 2 2
     61 
     62 1 2
     63 
     64 1 2 2
     65 
     66 2 2
     67 
     68 1 3 2
     69 
     70 2 4 4
     71 
     72 2 5
     73 
     74 1 10 5
     75 
     76 3 6 5
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 10
     83 0
     84 2
     85 4
     86 5
     87 ```
     88 
     89 Note
     90 
     91 In the first test case, you can first play at the $2$-nd casino. After that, you will have $2$ coins. Then you can play at the $1$-st casino, and the number of coins will increase to $3$. Finally, after playing at the $3$-rd casino, you will have $10$ coins — this is the maximum possible amount.
     92 
     93 In the second test case, you have no money, so you cannot earn more.
     94 
     95 In the fourth test case, it is beneficial to play at the $2$-nd casino right away and earn $4$ coins.