Drawing Rectangles - University Codesprint 4

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

struct Query {
    int type; int x; int l; int r;
    bool operator < (const Query &other) const {
        return x < other.x || (x == other.x && type < other.type);
    }
};
vector<Query> sweep;
vector<int> vals;

struct SegmentTree {
    int T[N << 2], lz[N << 2];

    void reset() {
        memset(T, 0, sizeof T);
        memset(lz, 0, sizeof lz);
    }
    #define mid ((l + r) >> 1)
    void push(int v, int l, int r) {
        if (!lz[v]) return;
        if (l < r) lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];
        T[v] += lz[v] * (r - l + 1);
        lz[v] = 0;
    }
    void upd(int v, int l, int r, int L, int R, int val) {
        push(v, l, r);
        if (R < l || L > r) return;
        if (L <= l && r <= R) { lz[v] = val; push(v, l, r); return; }
        upd(v << 1, l, mid, L, R, val);
        upd(v << 1 | 1, mid + 1, r, L, R, val);
        T[v] = T[v << 1] + T[v << 1 | 1];
    }
    void dfs(int v, int l, int r) {
        if (l == r) {
            vals.push_back(l); return;
        }
        push(v << 1, l, mid); push(v << 1 | 1, mid + 1, r);
        if (T[v << 1] > 0) dfs(v << 1, l, mid);
        if (T[v << 1 | 1] > 0) dfs(v << 1 | 1, mid + 1, r);
    }
    #undef mid
} seg;

int n;
vector<int> g[N];
bool checkL[N], checkR[N];
int matchL[N], matchR[N];

bool dfs(int u) {
    if (u == -1) return true;
    for (int &v : g[u]) {
        if (checkR[v]) continue;
        checkR[v] = true;
        if (dfs(matchR[v])) {
            matchL[u] = v; matchR[v] = u; return true;
        }
    }
    return false;
}

void trace(int u) {
    if (checkL[u]) return;
    checkL[u] = true;
    for (int &v : g[u]) {
        if (checkR[v]) continue;
        checkR[v] = true;
        trace(matchR[v]);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        sweep.push_back({+1, x1, y1, y2});
        sweep.push_back({-1, x2 + 1, y1, y2});
    }
    sort(sweep.begin(), sweep.end());

    int lstX = 0;
    for (int i = 0; i < sweep.size(); ) {
        int curX = sweep[i].x;
        // lstX -> curX - 1
        vals.clear();
        seg.dfs(1, 0, 3e5);
        for (int &y : vals) {
            for (int x = lstX; x <= curX - 1; ++x) {
                // add edge (x -> y)
                g[x].push_back(y);
            }
        }
        while(i < sweep.size() && sweep[i].x == curX) {
            seg.upd(1, 0, 3e5, sweep[i].l, sweep[i].r, sweep[i].type);
            ++i;
        }
        lstX = curX;
    }

    memset(matchL, -1, sizeof matchL);
    memset(matchR, -1, sizeof matchR);
    int rem = 3e5, prev_rem = 3e5 + 1;
    while(rem && rem < prev_rem) {
        prev_rem = rem;
        memset(checkR, 0, sizeof checkR);
        for (int row = 0; row <= 3e5; ++row) {
            if (matchL[row] == -1) {
                rem -= dfs(row);
            }
        }
    }

    int maxmatching = 0;
    memset(checkR, 0, sizeof checkR);
    for (int row = 0; row <= 3e5; ++row) {
        maxmatching += matchL[row] != -1;
        if (matchL[row] == -1) {
            trace(row);
        }
    }

    printf("%d\n", maxmatching);
    vector<int> vrow, vcol;
    for (int row = 0; row <= 3e5; ++row) if (!checkL[row]) vrow.push_back(row);
    for (int col = 0; col <= 3e5; ++col) if (checkR[col]) vcol.push_back(col);
    printf("%d\n", vrow.size());
    for (int &row : vrow) printf("%d ", row); printf("\n");
    printf("%d\n", vcol.size());
    for (int &col : vcol) printf("%d ", col); printf("\n");
}