Proficient.
Put your skills to the test.

Problem summary

After painting Q horizontal or vertical cell segments black in a huge grid, find the side length of the largest axis-aligned square containing only white cells.

Constraints

1 ≤ N,M ≤ 10⁹; 1 ≤ Q ≤ 50,000.

Worked example

An independently prepared example for this explanation.

6 5
4
1 2 1 5
1 4 5 4
5 2 5 2
1 2 1 5

3

Solution analysis

1. Binary-search the square side s. Its top-left cell can range over [1,N−s+1]×[1,M−s+1]. A black segment [x1,x2]×[y1,y2] forbids exactly the top-left rectangle [x1−s+1,x2]×[y1−s+1,y2], clipped to that allowed domain.
2. Test whether these forbidden rectangles cover every allowed top-left cell. Sweep their start and end-plus-one rows, adding or removing their column intervals in a lazy segment tree. Coordinate-compress column boundaries including 1 and M−s+2; each leaf represents a nonempty interval of integer columns. If the minimum coverage is zero on any nonempty row slab, a white s-square exists.
3. In the example a 3×3 white square survives to the left of the painted column. A side-4 square must intersect a painted segment. Repeated painting requests merely increase coverage counts and do not change which cells are forbidden.

Why it works

A square intersects a black segment exactly when its row and column ranges overlap that segment, yielding the derived forbidden top-left rectangle. The sweep maintains the exact number of such rectangles covering each compressed column interval throughout each row slab. A zero minimum therefore exists exactly when some legal square avoids every black cell. Feasibility is monotone because every white square contains smaller white squares, so binary search returns the maximum side.

Watch out. Painting coordinates are inclusive, so removals happen at end+1. Clip forbidden regions to valid top-left positions. A segment tree needs coverage minimum, not covered interval length. Use 64-bit coordinates.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<iostream>
#include<vector>
// Algorithm: Binary-search the square side s.
using namespace std;
struct Event{
    long long row,left,right;
    int delta;
    bool operator<(const Event&other)const{
        return row<other.row;
    }
};
class Coverage{
    vector<int>minimum,lazy;
    int size;
    void change(int node,int left,int right,int first,int last,int delta){
        if(first<=left&&right<=last){
            minimum[node]+=delta;
            lazy[node]+=delta;
            return;
        }
        int middle=(left+right)/2;
        if(first<=middle){
            change(2*node,left,middle,first,last,delta);
        }
        if(last>middle){
            change(2*node+1,middle+1,right,first,last,delta);
        }
        minimum[node]=lazy[node]+min(minimum[2*node],minimum[2*node+1]);
    }
    public:
    explicit Coverage(int count):minimum(4*count),lazy(4*count),size(count){
    }
    void change(int first,int last,int delta){
        change(1,0,size-1,first,last,delta);
    }
    int lowest()const{
        return minimum[1];
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,m;
    int q;
    cin>>n>>m>>q;
    vector<array<long long,4>>segments(q);
    for(auto&segment:segments){
        cin>>segment[0]>>segment[1]>>segment[2]>>segment[3];
    }
    auto feasible=[&](long long side){
        long long rows=n-side+1;
        long long columns=m-side+1;
        vector<Event>events;
        vector<long long>coordinate{1,columns+1};
        for(auto segment:segments){
            long long x1=max(1LL,segment[0]-side+1);
            long long x2=min(rows,segment[2]);
            long long y1=max(1LL,segment[1]-side+1);
            long long y2=min(columns,segment[3]);
            if(x1<=x2&&y1<=y2){
                events.push_back({x1,y1,y2+1,1});
                events.push_back({x2+1,y1,y2+1,-1});
                coordinate.push_back(y1);
                coordinate.push_back(y2+1);
            }
        }
        sort(coordinate.begin(),coordinate.end());
        coordinate.erase(unique(coordinate.begin(),coordinate.end()),coordinate.end());
        sort(events.begin(),events.end());
        Coverage coverage(static_cast<int>(coordinate.size())-1);
        long long row=1;
        int event=0;
        while(row<=rows){
            while(event<static_cast<int>(events.size())&&events[event].row==row){
                const Event&current=events[event++];
                int left=static_cast<int>(
                    lower_bound(coordinate.begin(),coordinate.end(),current.left)-coordinate.begin());
                int right=static_cast<int>(lower_bound(coordinate.begin(),coordinate.end(),current.right)-
                                coordinate.begin())-
                    1;
                coverage.change(left,right,current.delta);
            }
            if(coverage.lowest()==0){
                return true;
            }
            if(event==static_cast<int>(events.size())){
                return false;
            }
            row=events[event].row;
        }
        return false;
    };
    long long low=0;
    long long high=min(n,m);
    while(low<high){
        long long middle=low+(high-low+1)/2;
        if(feasible(middle)){
            low=middle;
        }
        else{
            high=middle-1;
        }
    }
    cout<<low<<'\n';
}