Submission #968813

#	Time	Username	Problem	Language	Result	Execution time	Memory
968813		vjudge1	Pyramid Base (IOI08_pyramid_base)	C++17	56 / 100	5023 ms	111200 KiB

pyramid_base

#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
#pragma GCC optimize(2)
#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[2*N],something2[2*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]);
}
vector<pair<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);
        pref[a].push_back({b,W[i]});
        if(D[i]<=m-k+1)
            pref[a].push_back({D[i],-W[i]});
        if(C[i]<=n-k+1)
            pref[C[i]].push_back({b,-W[i]}),something[C[i]]=1;
        if(D[i]<=m-k+1&&C[i]<=n-k+1)
            pref[C[i]].push_back({D[i],W[i]});
        something[a]=1;
    }
    reset(1,1,m-k+1);
    int ans=0;
    if(!something[1])
        ans=1;
    else for(int i=1;i<n-k+2;i++){
        if(something[i]) {
            for(auto [x,w]:pref[i])
                something2[x]+=w;
            for(auto [x,w]:pref[i])
                if(something2[x])
                    add(1,1,m-k+2,x,something2[x]),
                    something2[x]=0;
        }
        if(B[1]<=b) {
            ans=1;
            break;
        }
    }
    for(int i=1;i<=n-k+2;i++)
        if(something[i])
            pref[i].clear(),
            something[i]=0;
    return ans;
}
int read(){
    int res=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(47<c&&c<58)
        res=res*10+c-48,c=getchar();
    return res;
}
signed main(){
    long long XXX=chrono::steady_clock::now().time_since_epoch().count();
    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],C[i]++,D[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<<fixed<<setprecision(10)<<"Took: "<<(YYY-XXX)/1e9<<'s';
}

Compilation message (stderr)

pyramid_base.cpp: In function 'void reset(int, int, int)':
pyramid_base.cpp:10:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     reset(i*2,l,l+r>>1);
      |                 ~^~
pyramid_base.cpp:11:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     reset(i*2+1,l+r+2>>1,r);
      |                 ~~~^~
pyramid_base.cpp: In function 'void add(int, int, int, int, int)':
pyramid_base.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     if(pos>l+r>>1)
      |            ~^~
pyramid_base.cpp:17:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         add(i*2+1,l+r+2>>1,r,pos,x);
      |                   ~~~^~
pyramid_base.cpp:18:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     else add(i*2,l,l+r>>1,pos,x);
      |                    ~^~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:79:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int mid=l+r+1>>1;
      |                 ~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10