codeforces-scrape

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

1650C.md (3115B)


      1 Source: https://codeforces.com/problemset/problem/1650/C
      2 
      3 C. Weight of the System of Nested Segments
      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 On the number line there are $m$ points, $i$-th of which has integer coordinate $x_i$ and integer weight $w_i$. The coordinates of all points are different, and the points are numbered from $1$ to $m$.
     22 
     23 A sequence of $n$ segments $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ is called system of nested segments if for each pair $i, j$ ($1 \le i \lt j \le n$) the condition $l_i \lt l_j \lt r_j \lt r_i$ is satisfied. In other words, the second segment is strictly inside the first one, the third segment is strictly inside the second one, and so on.
     24 
     25 For a given number $n$, find a system of nested segments such that:
     26 
     27 * both ends of each segment are one of $m$ given points;
     28 * the sum of the weights $2\cdot n$ of the points used as ends of the segments is minimal.
     29 
     30 For example, let $m = 8$. The given points are marked in the picture, their weights are marked in red, their coordinates are marked in blue. Make a system of three nested segments:
     31 
     32 * weight of the first segment: $1 + 1 = 2$
     33 * weight of the second segment: $10 + (-1) = 9$
     34 * weight of the third segment: $3 + (-2) = 1$
     35 * sum of the weights of all the segments in the system: $2 + 9 + 1 = 12$
     36 
     37  ![](https://espresso.codeforces.com/3d2f150c1789082c2743f108263b96d90d653e03.png) System of three nested segments
     38 
     39 Input
     40 
     41 The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of input test cases.
     42 
     43 An empty line is written before each test case.
     44 
     45 The first line of each test case contains two positive integers $n$ ($1 \le n \le 10^5$) and $m$ ($2 \cdot n \le m \le 2 \cdot 10^5$).
     46 
     47 The next $m$ lines contain pairs of integers $x_i$ ($-10^9 \le x_i \le 10^9$) and $w_i$ ($-10^4 \le w_i \le 10^4$) — coordinate and weight of point number $i$ ($1 \le i \le m$) respectively. All $x_i$ are different.
     48 
     49 It is guaranteed that the sum of $m$ values over all test cases does not exceed $2 \cdot 10^5$.
     50 
     51 Output
     52 
     53 For each test case, output $n + 1$ lines: in the first of them, output the weight of the composed system, and in the next $n$ lines output exactly two numbers  — the indices of the points which are the endpoints of the $i$-th segment ($1 \le i \le n$). The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.
     54 
     55 If there are several ways to make a system of nested segments with minimal weight, output any of them.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 3
     63 
     64 3 8
     65 0 10
     66 -2 1
     67 4 10
     68 11 20
     69 7 -1
     70 9 1
     71 2 3
     72 5 -2
     73 
     74 3 6
     75 -1 2
     76 1 3
     77 3 -1
     78 2 4
     79 4 0
     80 8 2
     81 
     82 2 5
     83 5 -1
     84 3 -2
     85 1 0
     86 -2 0
     87 -5 -3
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 12
     94 2 6
     95 5 1
     96 7 8
     97 
     98 10
     99 1 6
    100 5 2
    101 3 4
    102 
    103 -6
    104 5 1
    105 4 2
    106 ```
    107 
    108 Note
    109 
    110 The first test case coincides with the example from the condition. It can be shown that the weight of the composed system is minimal.
    111 
    112 The second test case has only $6$ points, so you need to use each of them to compose $3$ segments.