对应NOIP难度的题解

#include <bits/stdc++.h>
using namespace std;
struct Interval {
    int start;
    int end;
};
bool compareIntervals(const Interval& a, const Interval& b) {
    if (a.start != b.start) {
        return a.start < b.start;
    }
    return a.end < b.end;
}
int main() {
    int C, N;
    if (!(cin >> C >> N)) return 0;
    vector<Interval> intervals(N);
    for (int i = 0; i < N; ++i) {
        cin >> intervals[i].start >> intervals[i].end;
        if (intervals[i].start > intervals[i].end) {
            swap(intervals[i].start, intervals[i].end);
        }
    }
    sort(intervals.begin(), intervals.end(), compareIntervals);
    vector<Interval> merged;
    if (N > 0) {
        merged.push_back(intervals[0]);
        for (int i = 1; i < N; ++i) {
            Interval& last = merged.back();
            Interval& curr = intervals[i];
            if (curr.start <= last.end) {
                last.end = max(last.end, curr.end);
            } else {
                merged.push_back(curr);
            }
        }
    }
    long long coveredCount = 0;
    for (const auto& m : merged) {
        int actualStart = max(m.start, 0);
        int actualEnd = min(m.end, C);
        if (actualStart <= actualEnd) {
            coveredCount += (long long)(actualEnd - actualStart + 1);
        }
    }
    long long totalPoints = (long long)C + 1;
    long long uncoveredCount = totalPoints - coveredCount;
    if (uncoveredCount < 0) uncoveredCount = 0;
    cout << uncoveredCount << endl;
    return 0;
}