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 |
|---|---|---|---|---|---|---|
| 2018 | Codeforces Round 975 (Div. 1) | FINISHED | False | 9000 | 48961523 | Sept. 27, 2024, 1:35 p.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 237 ) | E1 | Complex Segments (Easy Version) | PROGRAMMING | binary search data structures divide and conquer dsu greedy math sortings |
This is the easy version of the problem. In this version, the constraints on (n) and the time limit are lower. You can make hacks only if both versions of the problem are solved. A set of (closed) segments is complex if it can be partitioned into some subsets such that all the subsets have the same size; and a pair of segments intersects if and only if the two segments are in the same subset. You are given (n) segments (l_1, r_1, l_2, r_2, \ldots, l_n, r_n). Find the maximum size of a complex subset of these segments. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^3)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \le n \le 2 \cdot 10^4)) — the number of segments. The second line of each test case contains (n) integers (l_1, l_2, \ldots, l_n) ((1 \le l_i \le 2n)) — the left endpoints of the segments. The third line of each test case contains (n) integers (r_1, r_2, \ldots, r_n) ((l_i \leq r_i \le 2n)) — the right endpoints of the segments. It is guaranteed that the sum of (n) over all test cases does not exceed (2 \cdot 10^4). For each test case, output a single integer: the maximum size of a complex subset of the given segments. In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments. In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: (\{\{ 1, 5, 2, 4 \}, \{ 6, 9, 8, 10 \}\}). In the third test case, it is optimal to make a single group containing all the segments except the second. |
| Editorial of Codeforces Round 975 (Div. 1, Div. 2) |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 283287902 | Sparkle_Twilight | E1 | Sept. 27, 2024, 10:27 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 156 | 1740800 | ||
| 283271394 | hos.lyric | E1 | Sept. 27, 2024, 6:31 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 203 | 0 | ||
| 283260878 | Potassium | E1 | Sept. 27, 2024, 5:10 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 1374 | 102400 | ||
| 283261281 | Potassium | E1 | Sept. 27, 2024, 5:13 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 1421 | 1331200 | ||
| 283261320 | Potassium | E1 | Sept. 27, 2024, 5:13 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 1452 | 102400 | ||
| 283246141 | kiwihadron | E1 | Sept. 27, 2024, 3:47 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 1546 | 33689600 | ||
| 283293371 | Ormlis | E1 | Sept. 28, 2024, 1:05 a.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 2311 | 4710400 | ||
| 283236606 | alireza_kaviani | E1 | Sept. 27, 2024, 3:23 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 2312 | 37888000 | ||
| 283248084 | hos.lyric | E1 | Sept. 27, 2024, 3:52 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 2530 | 102400 | ||
| 283269080 | hos.lyric | E1 | Sept. 27, 2024, 6:11 p.m. | OK | C++17 (GCC 7-32) | TESTS | 15 | 3281 | 409600 | ||
| 283242197 | maspy | E1 | Sept. 27, 2024, 3:37 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 77 | 307200 | ||
| 283309260 | Nachia | E1 | Sept. 28, 2024, 5 a.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 93 | 512000 | ||
| 283304859 | A_G | E1 | Sept. 28, 2024, 4:08 a.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 109 | 716800 | ||
| 283261053 | _MASSIMO_ | E1 | Sept. 27, 2024, 5:11 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 124 | 102400 | ||
| 283228436 | jiangly | E1 | Sept. 27, 2024, 3:03 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 124 | 102400 | ||
| 283278961 | 244mhq | E1 | Sept. 27, 2024, 7:53 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 155 | 2150400 | ||
| 283241261 | greatpaul2008 | E1 | Sept. 27, 2024, 3:34 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 171 | 33689600 | ||
| 283248952 | rqoi031 | E1 | Sept. 27, 2024, 3:54 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 624 | 819200 | ||
| 283294639 | ainta | E1 | Sept. 28, 2024, 1:34 a.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 671 | 2560000 | ||
| 283248335 | RanRankeainie | E1 | Sept. 27, 2024, 3:53 p.m. | OK | C++20 (GCC 13-64) | TESTS | 15 | 718 | 24473600 | ||
| 283266933 | SparshMittal11 | E1 | Sept. 27, 2024, 5:54 p.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 140 | 1024000 | ||
| 283259278 | ecnerwala | E1 | Sept. 27, 2024, 5:01 p.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 624 | 0 | ||
| 283295630 | jinqihao2026 | E1 | Sept. 28, 2024, 1:55 a.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 671 | 14438400 | ||
| 283295717 | jinqihao2026 | E1 | Sept. 28, 2024, 1:56 a.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 703 | 14438400 | ||
| 283232974 | PEIMUDA | E1 | Sept. 27, 2024, 3:13 p.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 843 | 3788800 | ||
| 283240730 | Sugar_fan | E1 | Sept. 27, 2024, 3:33 p.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 1343 | 102400 | ||
| 283299866 | skip2004 | E1 | Sept. 28, 2024, 3 a.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 2202 | 9728000 | ||
| 283277943 | Dominater069 | E1 | Sept. 27, 2024, 7:40 p.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 15 | 2703 | 2867200 | ||
| 283250562 | rainboy | E1 | Sept. 27, 2024, 3:58 p.m. | OK | GNU C11 | TESTS | 15 | 249 | 8396800 | ||
| 283229605 | arvindf232 | E1 | Sept. 27, 2024, 3:06 p.m. | OK | Kotlin 1.7 | TESTS | 15 | 4764 | 84787200 | ||
| 283280139 | bnmanubharadwaj | E1 | Sept. 27, 2024, 8:09 p.m. | OK | Node.js | TESTS | 15 | 546 | 70860800 | ||
| 283266043 | sansen | E1 | Sept. 27, 2024, 5:47 p.m. | OK | Rust 2021 | TESTS | 15 | 359 | 102400 |
Back to search problems