oj.uz

Submission #968791

# Submission time Handle Problem Language Result Execution time Memory
968791 2024-04-24T04:49:46 Z vjudge1 Pyramid Base (IOI08_pyramid_base) C++17
0 / 100
 5000 ms 225960 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long
#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];
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]);
}
map<int,int>pref[2*N];
bool check(int k){
    for(int i=0;i<p;i++){
        int a=max(1ll,A[i]-k+1);
        int b=max(1ll,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];
    }
    reset(1,1,m-k+1);
    for(int i=1;i<n-k+2;i++){
        for(auto [x,w]:pref[i])
            if(x<=m-k+1)
                add(1,1,m-k+1,x,w);
        pref[i].clear();
        if(B[1]<=b)
            return 1;
    }
    return 0;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>b>>p;
    for(int i=0;i<p;i++)
        cin>>A[i]>>B2[i]>>C[i]>>D[i]>>W[i];
    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;
    }
    cout<<l;
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5009 ms 196852 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 5087 ms 225960 KB Time limit exceeded
2 Halted 0 ms 0 KB -