codeforces-scrape

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

1621B.md (2755B)


      1 Source: https://codeforces.com/problemset/problem/1621/B
      2 
      3 B. Integers Shop
      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 The integers shop sells $n$ segments. The $i$-th of them contains all integers from $l_i$ to $r_i$ and costs $c_i$ coins.
     22 
     23 Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it.
     24 
     25 After shopping, Vasya will get some more integers as a gift. He will get integer $x$ as a gift if and only if all of the following conditions are satisfied:
     26 
     27 * Vasya hasn't bought $x$.
     28 * Vasya has bought integer $l$ that is less than $x$.
     29 * Vasya has bought integer $r$ that is greater than $x$.
     30 
     31 Vasya can get integer $x$ as a gift only once so he won't have the same integers after receiving a gift.
     32 
     33 For example, if Vasya buys segment $[2, 4]$ for $20$ coins and segment $[7, 8]$ for $22$ coins, he spends $42$ coins and receives integers $2, 3, 4, 7, 8$ from these segments. He also gets integers $5$ and $6$ as a gift.
     34 
     35 Due to the technical issues only the first $s$ segments (that is, segments $[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$) will be available tomorrow in the shop.
     36 
     37 Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them.
     38 
     39 For each $s$ from $1$ to $n$, find how many coins will Vasya spend if only the first $s$ segments will be available.
     40 
     41 Input
     42 
     43 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     44 
     45 The first line of each test case contains the single integer $n$ ($1 \leq n \leq 10^5$) — the number of segments in the shop.
     46 
     47 Each of next $n$ lines contains three integers $l_i$, $r_i$, $c_i$ ($1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9$) — the ends of the $i$-th segments and its cost.
     48 
     49 It is guaranteed that the total sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     50 
     51 Output
     52 
     53 For each test case output $n$ integers: the $s$-th ($1 \leq s \leq n$) of them should be the number of coins Vasia will spend in the shop if only the first $s$ segments will be available.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 3
     61 
     62 2
     63 
     64 2 4 20
     65 
     66 7 8 22
     67 
     68 2
     69 
     70 5 11 42
     71 
     72 5 11 42
     73 
     74 6
     75 
     76 1 4 4
     77 
     78 5 8 9
     79 
     80 7 8 7
     81 
     82 2 10 252
     83 
     84 1 11 271
     85 
     86 1 10 1
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 20
     93 42
     94 42
     95 42
     96 4
     97 13
     98 11
     99 256
    100 271
    101 271
    102 ```
    103 
    104 Note
    105 
    106 In the first test case if $s = 1$ then Vasya can buy only the segment $[2, 4]$ for $20$ coins and get $3$ integers.
    107 
    108 The way to get $7$ integers for $42$ coins in case $s = 2$ is described in the statement.
    109 
    110 In the second test case note, that there can be the same segments in the shop.