oj.uz

Submission #969303

# Submission time Handle Problem Language Result Execution time Memory
969303 2024-04-24T22:41:37 Z vjudge1 Pyramid Base (IOI08_pyramid_base) C++17
45 / 100
 1295 ms 166000 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 124004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 124248 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 124000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 123988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 123984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 123992 KB Output is correct
2 Correct 47 ms 123996 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 124000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 124764 KB Output is correct
2 Correct 57 ms 125264 KB Output is correct
3 Correct 52 ms 125288 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 130132 KB Output is correct
2 Correct 187 ms 131156 KB Output is correct
3 Correct 162 ms 131116 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 143568 KB Output is correct
2 Correct 106 ms 133208 KB Output is correct
3 Correct 165 ms 149496 KB Output is correct
4 Correct 544 ms 160464 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 157388 KB Output is correct
2 Correct 936 ms 163448 KB Output is correct
3 Correct 137 ms 141260 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 144600 KB Output is correct
2 Correct 1221 ms 165804 KB Output is correct
3 Correct 1197 ms 165312 KB Output is correct
4 Correct 1295 ms 166000 KB Output is correct
5 Correct 1285 ms 165720 KB Output is correct
6 Correct 93 ms 140724 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 651 ms 140116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 789 ms 147280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 908 ms 154244 KB Output isn't correct
2 Halted 0 ms 0 KB -