#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll INF=1e18;
struct Node{
int maxv, lmax, rmax, lz, s, f;
Node() : maxv(0), lmax(0), rmax(0), lz(0), s(0), f(0) {}
Node& operator=(const Node &rhs){
maxv=rhs.maxv, lmax=rhs.lmax, rmax=rhs.rmax;
lz=rhs.lz, val=rhs.val;
return *this;
}
Node operator+(const Node &rhs) const{
Node ret;
ret.val=max(val,ret.val);
ret.maxv=max(maxv,rhs.maxv);
ret.maxv=max(ret.maxv,rmax+rhs.lmax);
ret.lmax=lmax, ret.rmax=rhs.rmax;
if(lmax==f-s+1) ret.lmax+=rhs.lmax;
if(rhs.rmax==rhs.f-rhs.s+1) ret.rmax+=rmax;
return ret;
}
};
struct SegTree{
vector<ll> tree, lazy;
int base;
SegTree(){
tree.resize(2097155);
lazy.resize(2097155);
}
void setup(int a){
base=1;
while(base<a) base<<=1;
for(int i=1 ; i<base*2 ; i++) tree[i]=lazy[i]=0;
for(int i=base+a ; i<base*2 ; i++) tree[i]=INF;
for(int i=base-1 ; i>=1 ; i--) tree[i]=min(tree[i*2],tree[i*2+1]);
base--;
}
void propagate(int ns, int nf, int num){
if(lazy[num]!=0){
if(ns<nf){
lazy[num*2]+=lazy[num];
lazy[num*2+1]+=lazy[num];
}
tree[num]+=lazy[num];
lazy[num]=0;
}
}
ll query(int ns=1, int nf=-1, int num=1){
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
return tree[num];
}
void add_value(ll val, int st, int fn, int ns=1, int nf=-1, int num=1){
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
if(ns>fn || nf<st) return;
if(st<=ns && nf<=fn){
lazy[num]+=val;
propagate(ns,nf,num);
return;
}
int mid=(ns+nf)>>1;
add_value(val,st,fn,ns,mid,num*2);
add_value(val,st,fn,mid+1,nf,num*2+1);
tree[num]=min(tree[num*2],tree[num*2+1]);
}
};
struct SegTree2{
vector<Node> tree;
int base;
SegTree2(){
tree.resize(2097155);
}
void setup(int a){
base=1;
while(base<a) base<<=1;
for(int i=base+a-1 ; i>=base ; i--) tree[i].maxv=tree[i].rmax=tree[i].lmax=1, tree[i].s=tree[num].f=i;
for(int i=base-1 ; i>=1 ; i--){
tree[i]=tree[i*2]+tree[i*2+1];
tree[i].s=tree[i*2].s;
tree[i].f=tree[i*2+1].f;
}
base--;
}
int query(int ns=1, int nf=-1, int num=1){
return tree[num].maxv;
}
void update(int val, int st, int fn, int ns=1, int nf=-1, int num=1){
if(nf==-1) nf=base+1;
if(ns>fn || nf<st) return;
if(st<=ns && nf<=fn){
tree[num].lz+=val;
if(tree[num].lz) tree[num].maxv=tree[num].lmax=tree[num].rmax=0;
else if(ns<nf) tree[num]=tree[num*2]+tree[num*2+1];
else if(ns==nf) tree[num].maxv=tree[num].lmax=tree[num].rmax=1;
return;
}
int mid=(ns+nf)>>1;
update(val,st,fn,ns,mid,num*2);
update(val,st,fn,mid+1,nf,num*2+1);
if(tree[num].lz) tree[num].maxv=tree[num].lmax=tree[num].rmax=0;
else tree[num]=tree[num*2]+tree[num*2+1];
}
};
struct A{
int x1, y1, x2, y2, c;
A(){}
A(int t1, int t2, int t3, int t4, int t5) : x1(t1), y1(t2), x2(t3), y2(t4), c(t5) {}
};
bool cmp(const A &lhs, const A &rhs){
return lhs.y1<rhs.y1;
}
bool cmp2(const A &lhs, const A &rhs){
return lhs.y2<rhs.y2;
}
int m, n, p;
ll b;
A ob[400005], ob2[400005];
bool pos(SegTree &T, int w)
{
T.setup(m-w+1);
int idx=1, idx2=1, st, fn, k;
for(int sy=1, fy=w ; fy<=n ; sy++, fy++){
while(idx<=p && ob[idx].y1>=sy && ob[idx].y1<=fy){
st=max(1,ob[idx].x1-w+1);
fn=min(m-w+1,ob[idx].x2);
T.add_value(ob[idx].c,st,fn);
idx++;
}
while(idx2<=p && ob2[idx2].y2<sy){
st=max(1,ob2[idx2].x1-w+1);
fn=min(m-w+1,ob2[idx2].x2);
T.add_value(-ob2[idx2].c,st,fn);
idx2++;
}
if(T.query()<=b) return true;
}
return false;
}
int main()
{
scanf("%d %d",&m,&n);
scanf("%lld",&b);
scanf("%d",&p);
for(int i=1 ; i<=p ; i++){
scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
ob2[i]=ob[i];
}
sort(ob+1,ob+1+p,cmp);
sort(ob2+1,ob2+1+p,cmp2);
if(b){
SegTree T;
int st=1, fn=min(m,n), mid, ans=0;
while(st<=fn){
mid=(st+fn)>>1;
if(pos(T,mid)) st=mid+1, ans=mid;
else fn=mid-1;
}
printf("%d",ans);
return 0;
}
int idx1=1, idx2=1, ans=0;
SegTree2 T2;
T2.setup(m);
for(int s=1, f=1 ; s<=n ; s++){
for( ; idx1<=p && ob[idx1].y1<=f ; idx1++) T2.update(1,ob[idx1].x1,ob[idx1].x2);
while(f<=n && f-s+1<=T2.query()){
ans=max(ans,f-s+1);
f++;
for( ; idx1<=p && ob[idx1].y1<=f ; idx1++) T2.update(1,ob[idx1].x1,ob[idx1].x2);
}
if(f>n) ans=max(ans,min(f-s,T2.query()));
for( ; idx2<=p && ob2[idx2].y2<=s ; idx2++) T2.update(-1,ob2[idx2].x1,ob2[idx2].x2);
}
printf("%d",ans);
return 0;
}
Compilation message
pyramid_base.cpp: In member function 'Node& Node::operator=(const Node&)':
pyramid_base.cpp:13:20: error: 'val' was not declared in this scope
13 | lz=rhs.lz, val=rhs.val;
| ^~~
pyramid_base.cpp:13:28: error: 'const struct Node' has no member named 'val'
13 | lz=rhs.lz, val=rhs.val;
| ^~~
pyramid_base.cpp: In member function 'Node Node::operator+(const Node&) const':
pyramid_base.cpp:18:13: error: 'struct Node' has no member named 'val'
18 | ret.val=max(val,ret.val);
| ^~~
pyramid_base.cpp:18:21: error: 'val' was not declared in this scope
18 | ret.val=max(val,ret.val);
| ^~~
pyramid_base.cpp:18:29: error: 'struct Node' has no member named 'val'
18 | ret.val=max(val,ret.val);
| ^~~
pyramid_base.cpp: In member function 'void SegTree2::setup(int)':
pyramid_base.cpp:84:102: error: 'num' was not declared in this scope; did you mean 'enum'?
84 | for(int i=base+a-1 ; i>=base ; i--) tree[i].maxv=tree[i].rmax=tree[i].lmax=1, tree[i].s=tree[num].f=i;
| ^~~
| enum
pyramid_base.cpp: In function 'bool pos(SegTree&, int)':
pyramid_base.cpp:134:32: warning: unused variable 'k' [-Wunused-variable]
134 | int idx=1, idx2=1, st, fn, k;
| ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
155 | scanf("%d %d",&m,&n);
| ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
156 | scanf("%lld",&b);
| ~~~~~^~~~~~~~~~~
pyramid_base.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
157 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
pyramid_base.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
159 | scanf("%d %d %d %d %d",&ob[i].x1,&ob[i].y1,&ob[i].x2,&ob[i].y2,&ob[i].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
