1782E - Rectangle Shrinking - CodeForces Solution

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = int(b); i <= i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = int(b); i >= i##_; --i)

using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n;
struct rtg {
    int l, r, u, d, id;
    bool operator<(const rtg &b)const {
        return l < b.l;
    }
} ans[N], rec[N], cur[3];
void Clear() {
    fp(i, 1, n)
        ans[i].l = ans[i].r = ans[i].u = ans[i].d = ans[i].id = 0;
    memset(cur, 0, sizeof(cur));
}
void Solve() {
    scanf("%d", &n);
    fp(i, 1, n)
        scanf("%d%d%d%d", &rec[i].d, &rec[i].l, &rec[i].u, &rec[i].r), rec[i].id = i;
    sort(rec + 1, rec + n + 1);
    fp(i, 1, n) {
        rec[i].l = max(rec[i].l, min(cur[1].r, cur[2].r) + 1);
        if (rec[i].r <= cur[1].r) rec[i].d = 2;
        if (rec[i].r <= cur[2].r) rec[i].u = 1;
        if (rec[i].l > rec[i].r || rec[i].d > rec[i].u) continue;
        fp(j, rec[i].d, rec[i].u) {
            if (cur[j].r >= rec[i].l) rec[cur[j].id].r = rec[i].l - 1;
            cur[j].r = rec[i].r, cur[j].id = i;
        }
    }
    int sum = 0;
    fp(i, 1, n) {
        int id = rec[i].id;
        if (rec[i].l <= rec[i].r && rec[i].d <= rec[i].u)
            ans[id] = rec[i], sum += (rec[i].u - rec[i].d + 1) * (rec[i].r - rec[i].l + 1);
    }
    printf("%d\n", sum);
    fp(i, 1, n) printf("%d %d %d %d\n", ans[i].d, ans[i].l, ans[i].u, ans[i].r);
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve(), Clear();
    return 0;
}