1198E - Rectangle Painting 2 - CodeForces Solution

// #define FASTIO



#include <cstring>

#include <cassert>

#include <utility>

#include <iostream>

#include <cstdio>

#include <iomanip>

#include <bitset>

#include <chrono>

#include <functional>

#include <tuple>

#include <climits>

#include <limits>

#include <deque>

#include <list>

#include <array>

#include <stack>

#include <queue>

#include <random>

#include <complex>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <unordered_map>

#include <unordered_set>

#include <algorithm>



#define F first

#define S second 

#define pb push_back

#define endl "\n"



#ifdef FASTIO



#define pr(x) printf("%d", x)

#define ps    printf(" ")

#define endc  printf("\n")

#define pl(x) printf("%lld", x)

#define pf(x) printf("%lf", x)

#define sc(x) scanf("%d", &x)

#define sl(x) scanf("%lld", &x)

#define sf(x) scanf("%lf", &x)

#define IOS 



#endif



#ifndef FASTIO

    #define IOS { ios :: sync_with_stdio(false); cin.tie(0); }

#endif



#ifdef DEBUG

    #define dbg(s) {s;}

#endif



#ifndef DEBUG

    #define dbg(s)

#endif



using namespace std;



mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int grand(int x) { // from [0, n-1]

    return uniform_int_distribution<int>(0, x - 1)(rng);

}



#define int ll

#define i32 int32_t



#define all(v) (v).begin(),(v).end()



typedef long long ll;

typedef long double ld;

typedef pair< int, int > pii;

typedef pair< ll, ll > pll;



ll gcd(ll x, ll y) {

    if (x < y) return gcd(y, x);

    if (y == 0) return x;

    return gcd(y, x % y);

} 



const ll mod = 1e9 + 7;



ll modexp(ll x, ll ex) {

    ll ans = 1ll;

    while (ex > 0) {

        if (ex & 1ll) ans = (ans * x) % mod;

        ex >>= 1ll;

        x = (x * x) % mod;

    }

    return ans;

}



const int maxn = 200;



const ll inf = 1e9 + 7;



struct FlowEdge {

    int v, u;

    long long cap, flow = 0;

    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}

};



struct Dinic {

    const long long flow_inf = 1e18;

    vector<FlowEdge> edges;

    vector<vector<int>> adj;

    int n, m = 0;

    int s, t;

    vector<int> level, ptr;

    queue<int> q;



    Dinic(int n, int s, int t) : n(n), s(s), t(t) {

        adj.resize(n);

        level.resize(n);

        ptr.resize(n);

    }



    void add_edge(int v, int u, long long cap) {

        edges.emplace_back(v, u, cap);

        edges.emplace_back(u, v, 0);

        adj[v].push_back(m);

        adj[u].push_back(m + 1);

        m += 2;

    }



    bool bfs() {

        while (!q.empty()) {

            int v = q.front();

            q.pop();

            for (int id : adj[v]) {

                if (edges[id].cap - edges[id].flow < 1)

                    continue;

                if (level[edges[id].u] != -1)

                    continue;

                level[edges[id].u] = level[v] + 1;

                q.push(edges[id].u);

            }

        }

        return level[t] != -1;

    }



    long long dfs(int v, long long pushed) {

        if (pushed == 0)

            return 0;

        if (v == t)

            return pushed;

        for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {

            int id = adj[v][cid];

            int u = edges[id].u;

            if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)

                continue;

            long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));

            if (tr == 0)

                continue;

            edges[id].flow += tr;

            edges[id ^ 1].flow -= tr;

            return tr;

        }

        return 0;

    }



    long long flow() {

        long long f = 0;

        while (true) {

            fill(level.begin(), level.end(), -1);

            level[s] = 0;

            q.push(s);

            if (!bfs())

                break;

            fill(ptr.begin(), ptr.end(), 0);

            while (long long pushed = dfs(s, flow_inf)) {

                f += pushed;

            }

        }

        return f;

    }

};



int x1[maxn];

int y3[maxn];

int x2[maxn];

int y2[maxn];



vector < int > xs;

vector < int > ys;



bool col[maxn][maxn];



i32 main() {

    //freopen("<file>.in", "r", stdin);

    //freopen("<file>.out", "w", stdout);



    IOS;

    

    int n, m; cin >> n >> m;

    for (int j = 1; j <= m; j++) {

        cin >> x1[j] >> y3[j] >> x2[j] >> y2[j];

        x2[j]++; y2[j]++;

        xs.pb(x1[j]); xs.pb(x2[j]);

        ys.pb(y3[j]); ys.pb(y2[j]);

    }



    sort(xs.begin(), xs.end()); xs.resize(unique(all(xs)) - xs.begin());

    sort(ys.begin(), ys.end()); ys.resize(unique(all(ys)) - ys.begin());

    

    int src = 1, snk = 2, sh = 3, sh2 = xs.size() + 3;



    Dinic Z = *new Dinic(xs.size() + ys.size() + 10, src, snk);



    for (int j = 0; j + 1 < xs.size(); j++) {

        Z.add_edge(src, j + sh, xs[j + 1] - xs[j]);

    }

    for (int j = 0; j + 1 < ys.size(); j++) {

        Z.add_edge(j + sh2, snk, ys[j + 1] - ys[j]);

    }



    for (int j = 1; j <= m; j++) {

        int sx, ex, sy, ey;

        for (int i = 0; i < xs.size(); i++) {

            if (xs[i] == x1[j]) { sx = i; break; }

        }

        for (int i = 0; i < xs.size(); i++) {

            if (xs[i] == x2[j]) { ex = i - 1; break; }

        }

        for (int i = 0; i < ys.size(); i++) {

            if (ys[i] == y3[j]) { sy = i; break; }

        }

        for (int i = 0; i < ys.size(); i++) {

            if (ys[i] == y2[j]) { ey = i - 1; break; }

        }



        for (int x = sx; x <= ex; x++) {

            for (int y = sy; y <= ey; y++) {

                col[x][y] = true;

            }

        }

    }



    for (int i = 0; i + 1< xs.size(); i++) {

        for (int j = 0; j  + 1< ys.size(); j++) {

            if (!col[i][j]) continue;

            int vl = i + sh, vr = j + sh2;

            Z.add_edge(vl, vr, inf);

        }

    }



    cout << Z.flow() << endl;

}