Submission #969303

#	Time	Username	Problem	Language	Result	Execution time	Memory
969303		vjudge1	Pyramid Base (IOI08_pyramid_base)	C++17	45 / 100	1295 ms	166000 KiB

pyramid_base

#include<bits/stdc++.h>
using namespace std;
int n,m,b,p;
namespace zero{
    struct info{
        int minv,minc,lz;
        info(){minv=lz=minc=0;}
        info(int sz){minv=lz=0,minc=sz;}
        info(info a,info b){
            minv=min(a.minv,b.minv);
            minc=lz=0;
            if(a.minv==minv)
                minc+=a.minc;
            if(b.minv==minv)
                minc+=b.minc;
        }
    } T[1<<21];
    void pd(int i,bool b){
        if(T[i].lz){
            T[i].minv+=T[i].lz;
            if(b)
                T[i*2].lz+=T[i].lz,T[i*2+1].lz+=T[i].lz;
            T[i].lz=0;
        }
    }
    void update(int i,int l,int r,int ql,int qr,int k){
        if(ql<=l&&r<=qr)
            return T[i].lz+=k,pd(i,l-r);
        pd(i,l-r);
        if(ql>r||l>qr)
            return;
        update(i*2,l,l+r>>1,ql,qr,k);
        update(i*2+1,l+r+2>>1,r,ql,qr,k);
        T[i]=info(T[i*2],T[i*2+1]);
    }
    void build(int i,int l,int r){
        T[i]=info(r-l+1);
        if(l-r) build(i*2,l,l+r>>1),
            build(i*2+1,l+r+2>>1,r);
    }
    vector<pair<int,int>> add[1<<20],rem[1<<20];
    int calc(){
        int ans=0,l=1,r=0;
        build(1,0,m);
        for(int i=0;i<p;i++){
            int a,b,c,d,e;
            cin>>a>>b>>c>>d>>e;
            add[a].push_back({b,d});
            rem[c].push_back({b,d});
        }
        while(r<=n){
            int A=r-l+1,B=T[1].minc-1;
            ans=max(ans,min(A,B));
            if(A<B){
                r++;
                for(auto[i,j]:add[r])
                    update(1,0,m,i,j,1);
            } else {
                for(auto[i,j]:rem[l])
                    update(1,0,m,i,j,-1);
                l++;
            }
        }
        return ans;
    }
}
namespace notzero{
    #define N 1<<20
    #define M 7<<16
    int S[2*N],B[2*N],A[M],B2[M],C[M],D[M],W[M],STUFF[N],SMTH[N],SMTH2[N];
    void reset(int i,int l,int r){
        S[i]=B[i]=0;
        if(l==r) return void(STUFF[l]=i);
        reset(i*2,l,l+r>>1);
        reset(i*2+1,l+r+2>>1,r);
    }
    void add(int pos,int x){
        pos=STUFF[pos];
        S[pos]=B[pos]+=x;
        pos/=2;
        while(pos){
            S[pos]=S[pos*2]+S[pos*2+1];
            B[pos]=min(B[pos*2],B[pos*2+1]+S[pos*2]);
            pos/=2;
        }
    }
    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]}),SMTH[C[i]]=1;
            if(D[i]<=m-k+1&&C[i]<=n-k+1)
                pref[C[i]].push_back({D[i],W[i]});
            SMTH[a]=1;
        }
        reset(1,1,m-k+1);
        int ans=0;
        if(!SMTH[1])
            ans=1;
        else for(int i=1;i<n-k+2;i++){
            if(SMTH[i]) {
                for(auto [x,w]:pref[i])
                    SMTH2[x]+=w;
                for(auto [x,w]:pref[i])
                    if(SMTH2[x]) {
                        w=STUFF[x];
                        S[w]=B[w]+=SMTH2[x];
                        SMTH2[x]=0;
                        w/=2;
                        while(w){
                            S[w]=S[w*2]+S[w*2+1];
                            B[w]=min(B[w*2],B[w*2+1]+S[w*2]);
                            w/=2;
                        }
                    }
            }
            if(B[1]<=b) {
                ans=1;
                break;
            }
        }
        for(int i=1;i<=n-k+2;i++)
            if(SMTH[i])
                pref[i].clear(),
                SMTH[i]=0;
        return ans;
    }
    int calc(){
        b=min(b,7000*p);
        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;
        }
        return l;
    }
    #undef N
    #undef M
}
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;
    if(b)
        cout<<notzero::calc();
    else cout<<zero::calc();
    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 zero::update(int, int, int, int, int, int)':
pyramid_base.cpp:32:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         update(i*2,l,l+r>>1,ql,qr,k);
      |                      ~^~
pyramid_base.cpp:33:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         update(i*2+1,l+r+2>>1,r,ql,qr,k);
      |                      ~~~^~
pyramid_base.cpp: In function 'void zero::build(int, int, int)':
pyramid_base.cpp:38:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         if(l-r) build(i*2,l,l+r>>1),
      |                             ~^~
pyramid_base.cpp:39:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             build(i*2+1,l+r+2>>1,r);
      |                         ~~~^~
pyramid_base.cpp: In function 'void notzero::reset(int, int, int)':
pyramid_base.cpp:74:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         reset(i*2,l,l+r>>1);
      |                     ~^~
pyramid_base.cpp:75:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         reset(i*2+1,l+r+2>>1,r);
      |                     ~~~^~
pyramid_base.cpp: In function 'int notzero::calc()':
pyramid_base.cpp:141:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |             int mid=l+r+1>>1;
      |                     ~~~^~

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