Educational Codeforces Round 4 D. The Union of k-Segments

問題

codeforces.com

解法

未だに問題の意味が正確にはわからないのでアレなんですが, 現れる数ごとに区間が重なっている数を +1, -1 していって, 重なる数が k 以上のところを取り出していけば良いです。

int main() {
    int n, k;
    cin >> n >> k;
    vector<pii> memo;
    for (int i = 0; i < n; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        memo.emplace_back(l, 0);
        memo.emplace_back(r, 1);
    }
    sort(memo.begin(), memo.end());
    vector<pii> ans;
    int cnt = 0;
    for (auto p : memo) {
        if (p.second == 0) {
            if (++cnt == k) ans.emplace_back(p.first, 0);
        } else {
            if (cnt-- == k) ans.back().second = p.first;
        }
    }
    cout << ans.size() << endl;
    for (auto p : ans) printf("%d %d\n", p.first, p.second);
    return 0;
}