IOI '08 P4 - Teleporters

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> L(n), R(n);
    for (int i = 0; i < n; ++i) cin >> L[i] >> R[i];
    auto getPartner = [&](int i) {return i ^ 1;};

    vector<pair<int, int>> ordered;
    for (int i = 0; i < n; ++i) {
        ordered.emplace_back(L[i], 2*i);
        ordered.emplace_back(R[i], 2*i+1);
    }
    sort(ordered.begin(), ordered.end());
    vector<int> nxt(2*n);
    for (int i = 0; i < 2*n; ++i) {
        nxt[ordered[i].second] = (i+1 == 2*n ? 2*n : ordered[i+1].second);
    }

    vector<int> edge(2*n);
    for (int i = 0; i < 2*n; ++i) edge[i] = nxt[getPartner(i)];

    // build cycles and chain
    int start = ordered.front().second;

    vector<bool> seen(2*n);
    vector<int> cycleSizes;

    auto findFrom = [&](int pos) {
        int sz = 0;
        while (pos != 2*n && !seen[pos]) {
            seen[pos] = true;
            pos = edge[pos];
            ++sz;
        }
        return sz;
    };

    int pathSize = findFrom(start);
    for (int first = 0; first < 2*n; ++first) {
        if (seen[first]) continue;
        cycleSizes.push_back(findFrom(first));
    }
    sort(cycleSizes.begin(), cycleSizes.end());
    while (m && !cycleSizes.empty()) {
        pathSize += cycleSizes.back() + 2;
        cycleSizes.pop_back();
        --m;
    }
    pathSize += 4 * (m/2) + (m&1);
    cout << pathSize << endl;
    return 0;
}