oj.uz

Submission #968796

# Submission time Handle Problem Language Result Execution time Memory
968796 2024-04-24T05:58:52 Z vjudge1 Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 1649 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace __gnu_pbds;
#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];
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]);
}
gp_hash_table<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);
        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];
        something[a]=something[c]=1;
    }
    something[1]=1;
    reset(1,1,m-k+1);
    if(pref[1].empty()) {
        for(int i=1;i<=n-k+2;i++)
            if(something[i])
                pref[i].clear(),
                something[i]=0;
        return 1;
    }
    for(int i=1;i<n-k+2;i++){
        if(i==n-k+1){
            cerr<<"HI";
        }
        if(something[i])
            for(auto [x,w]:pref[i])
                if(x<=m-k+1)
                    add(1,1,m-k+1,x,w);
        if(B[1]<=b) {
            for(int i=1;i<=n-k+2;i++)
                if(something[i])
                    pref[i].clear(),
                    something[i]=0;
            return 1;
        }
    }
    for(int i=1;i<=n-k+2;i++)
        if(something[i])
            pref[i].clear(),
            something[i]=0;
    return 0;
}
signed main(){
    long long XXX=chrono::steady_clock::now().time_since_epoch().count();
    cin.tie(0)->sync_with_stdio(0);
    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];
    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<<"Took: "<<(YYY-XXX)/1e9<<'s';
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 221952 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 222032 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 222248 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 222448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 224440 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 232168 KB Output is correct
2 Correct 282 ms 242516 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 242264 KB Output is correct
2 Correct 188 ms 232240 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 222732 KB Output is correct
2 Correct 203 ms 223248 KB Output is correct
3 Correct 190 ms 223272 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 227004 KB Output is correct
2 Correct 478 ms 226728 KB Output is correct
3 Correct 394 ms 226936 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 237064 KB Output is correct
2 Correct 276 ms 226776 KB Output is correct
3 Correct 268 ms 249928 KB Output is correct
4 Correct 855 ms 245784 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 247168 KB Output is correct
2 Correct 1299 ms 247508 KB Output is correct
3 Correct 265 ms 236412 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 237340 KB Output is correct
2 Correct 1598 ms 247004 KB Output is correct
3 Correct 1529 ms 246804 KB Output is correct
4 Correct 1615 ms 247624 KB Output is correct
5 Correct 1649 ms 247072 KB Output is correct
6 Correct 206 ms 234664 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 504 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 685 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 409 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -