oj.uz

Submission #969308

# Submission time Handle Problem Language Result Execution time Memory
969308 2024-04-24T23:22:14 Z vjudge1 Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 120312 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#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],STUFF[2*N],SMTH[2*N],SMTH2[2*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 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<<28);
    for(int i=0;i<p;i++)
        A[i]=read(),B2[i]=read(),C[i]=read(),D[i]=read(),W[i]=read(),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

pyramid_base.cpp: In function 'void reset(int, int, 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 'int main()':
pyramid_base.cpp:87:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid=l+r+1>>1;
      |                 ~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43608 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43608 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43612 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43868 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 54616 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 58200 KB Output is correct
2 Correct 114 ms 64340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 64592 KB Output is correct
2 Correct 40 ms 58192 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43864 KB Output is correct
2 Correct 28 ms 44448 KB Output is correct
3 Correct 25 ms 44124 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 56192 KB Output is correct
2 Correct 126 ms 56912 KB Output is correct
3 Correct 120 ms 57036 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 62472 KB Output is correct
2 Correct 52 ms 50116 KB Output is correct
3 Correct 114 ms 62676 KB Output is correct
4 Correct 481 ms 72632 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 71376 KB Output is correct
2 Correct 846 ms 74464 KB Output is correct
3 Correct 79 ms 59772 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 62964 KB Output is correct
2 Correct 1055 ms 76488 KB Output is correct
3 Correct 1028 ms 76432 KB Output is correct
4 Correct 1112 ms 76448 KB Output is correct
5 Correct 1160 ms 76756 KB Output is correct
6 Correct 36 ms 58832 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4441 ms 105496 KB Output is correct
2 Correct 729 ms 87636 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5053 ms 115284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 120312 KB Time limit exceeded
2 Halted 0 ms 0 KB -