Day 4. Rectangle

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
//#define int long long
#define uint __int128
#define mp make_pair
#define left left_compile
#define right right_compile

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int INF = (int)1e18;
const int md = 998244353;
const int MAXN = (int)1e6 + 10;
const int N = (int)2e5 + 111;
const int debug = 0;
const long double eps = 1e-7;

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

void init(){

    return;
}

vector<vector<int>> g;
//vector<vector<int>> Ops;
//vector<vector<int>> d;
//vector<vector<int>> pref;

int sum(int x1,int y1,int x2,int y2){
    return g[x2][y2] - g[x2][y1-1] - g[x1-1][y2] + g[x1-1][y1-1];
}

const int DX[] = {0,-1};
const int DY[] = {-1,0};

void solve_case(){
    int n,m;
    cin >> n >> m;

    g.resize(n+1,vector<int>(m+2,0));
    //d.resize(n+1,vector<int>(m+1,INF));
    //pref.resize(n+1,vector<int>(m+2,0));
    //Ops.resize(n+1,vector<int>(m+2));

    int Q;
    cin >> Q;
    int x1,x2,y1,y2;
    for(int t = 0; t < Q; t++){
        cin >> x1 >> y1 >> x2 >> y2;
        for(int i = x1; i <= x2; i++){
            g[i][y1]++;
            g[i][y2+1]--;
        }
    }

    int cnt;

    for(int i = 1; i <= n; i++){
        cnt = 0;
        for(int j = 1; j <= m; j++){
            cnt += g[i][j];
            g[i][j] = (cnt > 0);
        }
    }

    int x,y;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            g[i][j] = g[i-1][j] + g[i][j-1] - g[i-1][j-1] + g[i][j];
        }
    }

    int ans = 0;
    bool found = false;
    ans = 0;

    for(int i = 1; i <= n && !found; i++){
        for(int j = 1; j <= m && !found; j++){
            for(int k = ans + 1; i + k - 1 <= n && j + k - 1 <= m; k++){
                if(sum(i,j,i+k-1,j+k-1))
                    break;
                ans = max(ans,k);
            }
        }
    }

//    assert(found);

    cout << ans;

    return;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    init();

    int tests = 1;
//    cin >> tests;

    for(int _ = 1; _ <= tests; _++){
//        n = _;
        solve_case();
    }

    return 0;
}