Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.
ContestId |
Name |
Phase |
Frozen |
Duration (Seconds) |
Relative Time |
Start Time |
---|---|---|---|---|---|---|
1462 | Codeforces Round 690 (Div. 3) | FINISHED | False | 7200 | 129137063 | Dec. 15, 2020, 2:35 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 7116 ) | F | The Treasure of The Segments | PROGRAMMING | binary search data structures greedy sortings |
B"Polycarp found n segments on the street. A segment with the index i is described by two integers l_i and r_i -- coordinates of the beginning and end of the segment, respectively. Polycarp realized that he didn't need all the segments, so he wanted to delete some of them. Polycarp believes that a set of k segments is good if there is a segment [l_i, r_i] ( 1 <= q i <= q k ) from the set, such that it intersects every segment from the set (the intersection must be a point or segment). For example, a set of 3 segments [[1, 4], [2, 3], [3, 6]] is good, since the segment [2, 3] intersects each segment from the set. Set of 4 segments [[1, 2], [2, 3], [3, 5], [4, 5]] is not good. Polycarp wonders, what is the minimum number of segments he has to delete so that the remaining segments form a good set? The first line contains a single integer t ( 1 <= q t <= q 2 cdot 10^5 ) -- number of test cases. Then t test cases follow. The first line of each test case contains a single integer n ( 1 <= q n <= q 2 cdot 10^5 ) -- the number of segments. This is followed by n lines describing the segments. Each segment is described by two integers l and r ( 1 <= q l <= q r <= q 10^9 ) -- coordinates of the beginning and end of the segment, respectively. It is guaranteed that the sum of n for all test cases does not exceed 2 cdot 10^5 . For each test case, output a single integer -- the minimum number of segments that need to be deleted in order for the set of remaining segments to become good. "... |
Codeforces Round #690 (Div. 3) Editorial |
No solutions yet.