ฐานปิรามิด: ตารางล้านคูณล้านที่ไม่ต้องแตะสักช่อง

// เฉลยชุดทดสอบย่อยชุดแรก งบเป็นศูนย์ และสิ่งกีดขวางไม่เกิน 1,000 ก้อน (35 คะแนน)
// งบเป็นศูนย์แปลว่าห้ามชนก้อนไหนเลย คำถามจึงเหลือแค่ "มีที่ว่างขนาดนี้ไหม"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int P; ll M, N;
vector<ll> x1_, y1_, x2_, y2_;

bool ok(ll s) {
    if (M - s + 1 < 1 || N - s + 1 < 1) return false;
    const ll XH = M - s + 1, YH = N - s + 1;
    // มุมล่างซ้ายที่น่าลองมีแค่ 1 กับขอบซ้ายของแต่ละก้อนที่เลื่อนมา s-1 ช่อง
    vector<ll> xs{1};
    for (int i = 0; i < P; i++) { ll v = x2_[i] + 1; if (v <= XH) xs.push_back(v); }
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());

    vector<pair<ll,ll>> bad;
    for (ll x : xs) {
        bad.clear();
        for (int i = 0; i < P; i++) {
            if (x + s - 1 < x1_[i] || x > x2_[i]) continue;          // ก้อนนี้ไม่ขวางที่คอลัมน์นี้
            ll lo = max(1LL, y1_[i] - s + 1), hi = min(YH, y2_[i]);
            if (lo <= hi) bad.push_back({lo, hi});
        }
        sort(bad.begin(), bad.end());
        ll cur = 1;                                                  // ไล่หาช่องว่างแรกที่ไม่มีใครทับ
        for (auto& [lo, hi] : bad) {
            if (lo > cur) break;
            cur = max(cur, hi + 1);
        }
        if (cur <= YH) return true;
    }
    return false;
}

int main() {
    ll B;
    scanf("%lld %lld %lld %d", &M, &N, &B, &P);
    x1_.resize(P); y1_.resize(P); x2_.resize(P); y2_.resize(P);
    for (int i = 0; i < P; i++) { ll c; scanf("%lld %lld %lld %lld %lld", &x1_[i], &y1_[i], &x2_[i], &y2_[i], &c); }
    ll lo = 0, hi = min(M, N);
    while (lo < hi) { ll md = (lo + hi + 1) / 2; if (ok(md)) lo = md; else hi = md - 1; }
    printf("%lld\n", lo);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int P; ll M,N,B;
vector<ll> X1,Y1,X2,Y2,C;
vector<int> byX1,byX2,byY1,byY2;
int SZ; vector<ll> mn,lz;
const ll INF=(ll)4e18;
void build(int k){
    SZ=1; while(SZ<k) SZ<<=1;
    mn.assign(2*SZ,0); lz.assign(2*SZ,0);
    for(int i=k;i<SZ;i++) mn[SZ+i]=INF;             // ใบส่วนเกินต้องเป็นอนันต์ ไม่ใช่ศูนย์
    for(int i=SZ-1;i>=1;i--) mn[i]=min(mn[2*i],mn[2*i+1]);
}
// บวกทั้งช่วงแบบไล่จากใบขึ้นราก ไม่ใช้การเรียกซ้ำ เพราะรอบนี้ถูกเรียกหลายสิบล้านครั้ง
void add(int l,int r,ll v){
    int L=l+SZ, R=r+SZ+1, l0=L, r0=R-1;
    while(L<R){
        if(L&1){ mn[L]+=v; lz[L]+=v; L++; }
        if(R&1){ --R; mn[R]+=v; lz[R]+=v; }
        L>>=1; R>>=1;
    }
    for(int i=l0>>1;i>=1;i>>=1) mn[i]=min(mn[2*i],mn[2*i+1])+lz[i];
    for(int i=r0>>1;i>=1;i>>=1) mn[i]=min(mn[2*i],mn[2*i+1])+lz[i];
}
vector<ll> cand; vector<int> klOf,krOf;
vector<ll> evX; vector<int> evI; vector<char> evAdd;
bool ok(ll s){
    if(M-s+1<1||N-s+1<1) return false;
    const ll YH=N-s+1, XH=M-s+1;
    // ผู้สมัครแกน y  รวมสองสายที่เรียงอยู่แล้ว จึงไม่ต้องเรียงใหม่ทุกรอบ
    cand.clear(); cand.push_back(1);
    { size_t a=0,b=0; ll va,vb;
      auto nextA=[&](){ while(a<(size_t)P){ int i=byY1[a]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); a++; if(lo<=hi){ va=lo; return true; } } return false; };
      auto nextB=[&](){ while(b<(size_t)P){ int i=byY2[b]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); b++; if(lo<=hi&&hi+1<=YH){ vb=hi+1; return true; } } return false; };
      bool ha=nextA(), hb=nextB();
      while(ha||hb){ ll v; if(!hb||(ha&&va<=vb)){ v=va; ha=nextA(); } else { v=vb; hb=nextB(); }
        if(cand.back()!=v) cand.push_back(v); } }
    int K=(int)cand.size(); build(K);
    // ดัชนีขอบล่าง/ขอบบนของแต่ละก้อน หาแบบสองตัวชี้ เพราะทั้งสองสายเรียงมาแล้ว
    { size_t p=0; for(int t=0;t<P;t++){ int i=byY1[t]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); if(lo>hi){ klOf[i]=-1; continue; }
        while(p+1<cand.size()&&cand[p+1]<=lo) p++; while(cand[p]>lo&&p>0) p--; klOf[i]=(int)p; } }
    { size_t p=0; for(int t=0;t<P;t++){ int i=byY2[t]; ll lo=max(1LL,Y1[i]-s+1), hi=min(YH,Y2[i]); if(lo>hi){ krOf[i]=-1; continue; }
        while(p+1<cand.size()&&cand[p+1]<=hi) p++; krOf[i]=(int)p; } }
    // เหตุการณ์แกน x  สองสายเรียงอยู่แล้วเช่นกัน จึงแค่ผสาน
    evX.clear(); evI.clear(); evAdd.clear();
    { size_t a=0,b=0;
      auto valA=[&](size_t t){ int i=byX1[t]; return max(1LL,X1[i]-s+1); };
      auto valB=[&](size_t t){ int i=byX2[t]; return min(XH,X2[i])+1; };
      auto usable=[&](int i){ ll xl=max(1LL,X1[i]-s+1), xr=min(XH,X2[i]); return klOf[i]>=0 && xl<=xr; };
      while(a<(size_t)P||b<(size_t)P){
        bool takeA;
        if(a>=(size_t)P) takeA=false; else if(b>=(size_t)P) takeA=true; else takeA = valA(a)<=valB(b);
        if(takeA){ int i=byX1[a]; if(usable(i)){ evX.push_back(valA(a)); evI.push_back(i); evAdd.push_back(1);} a++; }
        else { int i=byX2[b]; ll v=valB(b); if(usable(i)&&v<=XH){ evX.push_back(v); evI.push_back(i); evAdd.push_back(0);} b++; }
      } }
    size_t e=0; ll cur=1;
    while(cur<=XH){
        while(e<evX.size()&&evX[e]<=cur){ int i=evI[e]; add(klOf[i],krOf[i], evAdd[e]?C[i]:-C[i]); e++; }
        if(mn[1]<=B) return true;
        cur = (e<evX.size()) ? evX[e] : XH+1;
    }
    return false;
}
int main(){
    if(scanf("%lld %lld",&M,&N)!=2) return 0;
    scanf("%lld",&B); scanf("%d",&P);
    X1.resize(P);Y1.resize(P);X2.resize(P);Y2.resize(P);C.resize(P);
    klOf.assign(P,-1); krOf.assign(P,-1);
    for(int i=0;i<P;i++) scanf("%lld %lld %lld %lld %lld",&X1[i],&Y1[i],&X2[i],&Y2[i],&C[i]);
    byX1.resize(P);byX2.resize(P);byY1.resize(P);byY2.resize(P);
    for(int i=0;i<P;i++) byX1[i]=byX2[i]=byY1[i]=byY2[i]=i;
    sort(byX1.begin(),byX1.end(),[](int a,int b){return X1[a]<X1[b];});
    sort(byX2.begin(),byX2.end(),[](int a,int b){return X2[a]<X2[b];});
    sort(byY1.begin(),byY1.end(),[](int a,int b){return Y1[a]<Y1[b];});
    sort(byY2.begin(),byY2.end(),[](int a,int b){return Y2[a]<Y2[b];});
    ll lo=0,hi=min(M,N);
    while(lo<hi){ ll md=(lo+hi+1)/2; if(ok(md)) lo=md; else hi=md-1; }
    printf("%lld\n",lo);
}

const ll INF = (ll)4e18;
int SZ; vector<ll> mn, lz;

void build(int k){
    SZ = 1; while (SZ < k) SZ <<= 1;
    mn.assign(2 * SZ, 0); lz.assign(2 * SZ, 0);
    for (int i = k; i < SZ; i++) mn[SZ + i] = 0;   // <-- บักอยู่บรรทัดนี้ ใบส่วนเกินถูกปล่อยไว้ที่ศูนย์
    for (int i = SZ - 1; i >= 1; i--) mn[i] = min(mn[2 * i], mn[2 * i + 1]);
}

// ปลายทางที่บักโผล่ อยู่ในลูปกวาดเส้นของ ok()
if (mn[1] <= B) return true;   // mn[1] ถูกใบศูนย์กดไว้ตลอด บรรทัดนี้จึงตอบ true ทุกครั้ง

9 6
10
6
2 5 4 5 8
4 4 7 5 3
6 2 9 6 8
4 4 4 6 9
7 6 7 6 5
4 6 7 6 4