Submission #968787

#TimeUsernameProblemLanguageResultExecution timeMemory
968787vjudge1Pyramid Base (IOI08_pyramid_base)C++17
0 / 100
5065 ms231244 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #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]; 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]); } map<int,int>pref[2*N]; bool check(int k){ for(int i=0;i<p;i++){ int a=max(1ll,A[i]-k+1); int b=max(1ll,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]; } reset(1,1,m-k+1); for(int i=1;i<n-k+2;i++){ for(auto [x,w]:pref[i]) if(x<=m-k+1) add(1,1,m-k+1,x,w); pref[i].clear(); if(B[1]<=b) return 1; } return 0; } signed main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>m>>b>>p; for(int i=0;i<p;i++) cin>>A[i]>>B2[i]>>C[i]>>D[i]>>W[i]; 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; }

Compilation message (stderr)

pyramid_base.cpp: In function 'void reset(long long int, long long int, long long int)':
pyramid_base.cpp:9:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |     reset(i*2,l,l+r>>1);
      |                 ~^~
pyramid_base.cpp:10:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     reset(i*2+1,l+r+2>>1,r);
      |                 ~~~^~
pyramid_base.cpp: In function 'void add(long long int, long long int, long long int, long long int, long long int)':
pyramid_base.cpp:15:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     if(pos>l+r>>1)
      |            ~^~
pyramid_base.cpp:16:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         add(i*2+1,l+r+2>>1,r,pos,x);
      |                   ~~~^~
pyramid_base.cpp:17:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     else add(i*2,l,l+r>>1,pos,x);
      |                    ~^~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:51:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid=l+r+1>>1;
      |                 ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...