This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace __gnu_pbds;
#define N 1<<19
int S[4*N],B[4*N],n,m,p,b,A[N],B2[N],C[N],D[N],W[N],something[N];
void reset(int i,int l,int r){
S[i]=B[i]=0;
if(l==r) return;
reset(i*2,l,l+r>>1);
reset(i*2+1,l+r+2>>1,r);
}
void add(int i,int l,int r,int pos,int x){
if(l==r)
return void(S[i]=B[i]+=x);
if(pos>l+r>>1)
add(i*2+1,l+r+2>>1,r,pos,x);
else add(i*2,l,l+r>>1,pos,x);
S[i]=S[i*2]+S[i*2+1];
B[i]=min(B[i*2],S[i*2]+B[i*2+1]);
}
gp_hash_table<int,int>pref[2*N];
bool check(int k){
for(int i=0;i<p;i++){
int a=max(1,A[i]-k+1);
int b=max(1,B2[i]-k+1);
int c=min(C[i],n-k+1)+1;
int d=min(D[i],m-k+1)+1;
pref[a][b]+=W[i];
pref[a][d]-=W[i];
pref[c][b]-=W[i];
pref[c][d]+=W[i];
something[a]=something[c]=1;
}
something[1]=1;
reset(1,1,m-k+1);
if(pref[1].empty()) {
for(int i=1;i<=n-k+2;i++)
if(something[i])
pref[i].clear(),
something[i]=0;
return 1;
}
for(int i=1;i<n-k+2;i++){
if(i==n-k+1){
cerr<<"HI";
}
if(something[i])
for(auto [x,w]:pref[i])
if(x<=m-k+1)
add(1,1,m-k+1,x,w);
if(B[1]<=b)
return 1;
}
for(int i=1;i<=n-k+2;i++)
if(something[i])
pref[i].clear(),
something[i]=0;
return 0;
}
signed main(){
long long XXX=chrono::steady_clock::now().time_since_epoch().count();
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>b>>p;
b=min(b,1<<30);
for(int i=0;i<p;i++)
cin>>A[i]>>B2[i]>>C[i]>>D[i]>>W[i];
if(!b) for(int i=0;i<p;i++)
W[i]=1;
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;
cerr<<"DONE1\n";
}
cout<<l<<'\n';
long long YYY=chrono::steady_clock::now().time_since_epoch().count();
cerr<<"Took: "<<(YYY-XXX)/1e9<<'s';
}
Compilation message (stderr)
pyramid_base.cpp: In function 'void reset(int, int, int)':
pyramid_base.cpp:11:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
11 | reset(i*2,l,l+r>>1);
| ~^~
pyramid_base.cpp:12:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | reset(i*2+1,l+r+2>>1,r);
| ~~~^~
pyramid_base.cpp: In function 'void add(int, int, int, int, int)':
pyramid_base.cpp:17:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | if(pos>l+r>>1)
| ~^~
pyramid_base.cpp:18:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | add(i*2+1,l+r+2>>1,r,pos,x);
| ~~~^~
pyramid_base.cpp:19:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | else add(i*2,l,l+r>>1,pos,x);
| ~^~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:73:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid=l+r+1>>1;
| ~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |