Approach
Sorting and greedy selection
For ABC408 C — Not All Covered, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 67 lines of C++ from the credited upstream file abc408_c.cpp.
- The implementation visibly relies on sequence storage.
- 5 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <vector>4 5using namespace std;6using ui = unsigned int;7 8int main() {9 ui n, m;10 cin >> n >> m;11 12 vector<pair<ui, ui>> ranges(m);13 for (ui i = 0; i < m; i++) {14 cin >> ranges[i].first >> ranges[i].second;15 }16 17 sort(ranges.begin(), ranges.end());18 19 ui current_end = 0;20 bool has_uncovered = false;21 22 for (ui i = 0; i < m; i++) {23 if (ranges[i].first > current_end + 1) {24 if (current_end < n) {25 has_uncovered = true;26 break;27 }28 }29 current_end = max(current_end, ranges[i].second);30 }31 32 if (current_end < n) has_uncovered = true;33 34 if (has_uncovered) {35 cout << 0 << endl;36 return 0;37 }38 39 vector<pair<ui, ui>> diff;40 for (ui i = 0; i < m; i++) {41 diff.push_back({ranges[i].first, 1});42 diff.push_back({ranges[i].second + 1, -1});43 }44 sort(diff.begin(), diff.end());45 46 ui min_coverage = m + 1;47 ui current_coverage = 0;48 49 for (ui i = 0; i < diff.size(); i++) {50 ui pos = diff[i].first;51 ui delta = 0;52 53 while (i < diff.size() && diff[i].first == pos) {54 delta += diff[i].second;55 i++;56 }57 i--;58 59 current_coverage += delta;60 61 if (pos >= 1 && pos <= n && current_coverage > 0)62 min_coverage = min(min_coverage, current_coverage);63 }64 65 cout << min_coverage << endl;66 return 0;67}