1313D - Happy New Year - CodeForces Solution

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> events;

    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        --x;
        events.push_back({x, i, 1});
        events.push_back({y, i, 0});
    }

    sort(events.begin(), events.end(), [&](auto x, auto y){
				if (x[0] < y[0])return true;
				else if (x[0] == y[0])return x[2] < y[2];
				else return false;
		});
    vector<int> dp((1 << 8), -(int)1e9);
    vector<int> used(8, -1);
    dp[0] = 0;

    for (int p = 0; p < (int)events.size(); p++) {
        int index = events[p][1];
        int dist = (p == (int)events.size() - 1 ? 0 : events[p + 1][0] - events[p][0]);
        int type = events[p][2];

        if (type) {
            int bit;
            for (int i = 0; i < 8; i++) {
                if (used[i] == -1) {
                    used[i] = index;
                    bit = i;
                    break;
                }
            }

            for (int mask = 255; mask >= 0; mask--) {
                if (mask & (1 << bit)) {
                    dp[mask] = dp[mask ^ (1 << bit)] + dist *( __builtin_popcount(mask) & 1);
                } else {
                    dp[mask] += dist *( __builtin_popcount(mask) & 1);
                }
            }
        } else {
            int bit;
            for (int i = 0; i < 8; i++) {
                if (used[i] == index) {
                    used[i] = -1;
                    bit = i;
                    break;
                }
            }
            //assert(bit != -1);
            for (int mask = 0; mask < 256; mask++) {
                if (mask & (1 << bit)) {
                    dp[mask] = -(int)1e9;
                } else {
                    dp[mask] = max(dp[mask], dp[mask ^ (1 << bit)]) + dist *( __builtin_popcount(mask) & 1);
                }
            }
        }
    }

    cout << dp[0];
    return 0;
}