#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int n,m,type,lim;
struct IT_node
{
int res,lz,l,r,lseg,rseg,mi;
bool full;
void modify(int k)
{
lz+=k; l+=k; r+=k; mi+=k;
}
};
IT_node operator + (IT_node a,IT_node b)
{
IT_node c;
c.l=a.l; c.r=b.r; c.mi=min(a.mi,b.mi);
c.full=(a.full && b.full && a.l==b.r);
if(a.l==c.mi) c.lseg=a.lseg+((a.full && b.l==a.l) ? b.lseg : 0);
else c.lseg=0;
if(b.r==c.mi) c.rseg=b.rseg+((b.full && b.r==a.r) ? a.rseg : 0);
else c.rseg=0;
c.lz=c.res=0;
if(a.mi==c.mi) c.res=max(c.res,a.res);
if(b.mi==c.mi) c.res=max(c.res,b.res);
if(a.r==c.mi && b.l==c.mi) c.res=max(c.res,a.rseg+b.lseg);
return c;
}
struct Interval_Tree
{
IT_node st[4*N];
void build(int id,int l,int r)
{
if(l==r) { st[id]={ 1,0,0,0,1,1,0,1 }; return ; }
int mid=(l+r)>>1,jd=id<<1;
build(jd,l,mid); build(jd+1,mid+1,r);
st[id]=st[jd]+st[jd+1];
}
void down(int id)
{
if(st[id].lz==0) return ;
st[id<<1].modify(st[id].lz); st[(id<<1)+1].modify(st[id].lz);
st[id].lz=0;
}
void update(int id,int l,int r,int u,int v,int k)
{
if(u<=l && r<=v) { st[id].modify(k); return ; }
down(id);
int mid=(l+r)>>1,jd=id<<1;
if(v<=mid) update(jd,l,mid,u,v,k);
else if(u>mid) update(jd+1,mid+1,r,u,v,k);
else
{
update(jd,l,mid,u,mid,k);
update(jd+1,mid+1,r,mid+1,v,k);
}
st[id]=st[jd]+st[jd+1];
}
} IT;
struct SUB0
{
int cnt,i;
vector <II> L[N],R[N];
bool check(int k)
{
IT.build(1,1,n);
for(i=1;i<=m;i++)
{
for(II u:L[i]) IT.update(1,1,n,u.fst,u.snd,1);
if(i>=k)
{
for(II u:R[i-k]) IT.update(1,1,n,u.fst,u.snd,-1);
if(IT.st[1].mi==0 && IT.st[1].res>=k) return 1;
}
}
return 0;
}
void Work()
{
cin>>cnt;
while(cnt--)
{
int x1,y1,x2,y2,k;
cin>>x1>>y1>>x2>>y2>>k;
L[y1].push_back({ x1,x2 });
R[y2].push_back({ x1,x2 });
}
int l=0,r=min(n,m);
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid; else r=mid-1;
}
cout<<l;
}
} Sub0;
struct SUB1
{
ll st[4*N],lz[4*N],p,i;
struct pt { int l,r,k; };
vector <pt> L[N],R[N];
struct rec { int x1,y1,x2,y2,k; } a[N];
void modify(int id,int k)
{
st[id]+=k;
lz[id]+=k;
}
void down(int id)
{
modify(id*2,lz[id]); modify(id*2+1,lz[id]);
lz[id]=0;
}
void update(int id,int l,int r,int u,int v,int k)
{
if(u>r || v<l) return ;
if(u<=l && r<=v) { modify(id,k); return ; }
down(id);
int mid=(l+r)>>1;
update(id*2,l,mid,u,v,k); update(id*2+1,mid+1,r,u,v,k);
st[id]=min(st[id*2],st[id*2+1]);
}
bool check(int k)
{
for(i=1;i<=m;i++) L[i].clear(),R[i].clear();
for(i=1;i<=p;i++)
{
int x1=a[i].x1,y1=a[i].y1,x2=min(n,a[i].x2+k-1),y2=min(m,a[i].y2+k-1);
L[y1].push_back({ x1,x2,a[i].k });
R[y2].push_back({ x1,x2,a[i].k });
}
memset(st,0,sizeof(st));
memset(lz,0,sizeof(lz));
for(i=1;i<=m;i++)
{
for(pt u:L[i]) update(1,k,n,u.l,u.r,u.k);
if(i>=k)
{
for(pt u:R[i-k]) update(1,k,n,u.l,u.r,-u.k);
if(st[1]<=lim) return 1;
}
}
return 0;
}
void Work()
{
cin>>p;
for(i=1;i<=p;i++) cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2>>a[i].k;
int l=0,r=min(n,m);
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid; else r=mid-1;
}
cout<<l;
}
} Sub1;
int main()
{
// freopen("pyramid_base.inp","r",stdin);
// freopen("pyramid_base.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>lim;
if(lim==0) Sub0.Work();
else Sub1.Work();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
98904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
98908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
98908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
100952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
107240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
559 ms |
164680 KB |
Output is correct |
| 2 |
Correct |
552 ms |
164684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
574 ms |
164700 KB |
Output is correct |
| 2 |
Correct |
570 ms |
164652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
161020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
252 ms |
159800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
386 ms |
166292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
447 ms |
168908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
401 ms |
166992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5100 ms |
181584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5021 ms |
189520 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5023 ms |
196932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
