oj.uz

Submission #1065137

# Submission time Handle Problem Language Result Execution time Memory
1065137 2024-08-19T00:20:10 Z YassirSalama Fish 2 (JOI22_fish2) C++17
0 / 100
 38 ms 28536 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
template<typename T> 
void dbg(const T& t){
    cout<<t<<endl;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
    cout<<t<<" , ";
    dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : ";dbg(__VA_ARGS__);
pair<int,int> f(pair<int,int> a,pair<int,int> b){
    if(a.F>=b.F) return a;
    else return b;
}
vector<int> v(1e5+100);
vector<vector<pair<int,int>>> st(1e5+1,vector<pair<int,int>>(30,make_pair(1e18,1e18)));
int lg=30;
pair<int,int> query(int l,int r){
    int k=r-l+1;
    k=log2(k);
    return f(st[l][k],st[r-(1LL<<k)+1][k]);
}
int ans=0;
int pref[(int)1e5+100];
int sum(int l,int r){
    if(l==0) return pref[r];
    return pref[r]-pref[l-1];
}

void solve(int l,int r,int par){
    if(l>r) return;
    pair<int,int> a=query(l,r);
    if(sum(l,r)>=v[par]) {
        ans++;
        solve(l,a.S-1,a.S);
        solve(a.S+1,r,a.S);
    }
}
int main(){
    int n;
    cin>>n;
    v[n]=0;
    for(int i=0;i<n;i++){
        cin>>v[i];
        pref[i]=v[i];
        if(i) pref[i]+=pref[i-1];
    }
    for(int i=0;i<n;i++){
        st[i][0]={v[i],i};
    }
    for(int p=1;p<lg;p++){
        for(int i=0;i+(1LL<<p)<=n;i++){
            st[i][p]=f(st[i][p-1],st[i+(1LL<<(p-1))][p-1]);
        }
    }    
    solve(0,n-1,n);
    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Incorrect 38 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Incorrect 38 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27992 KB Output is correct
2 Incorrect 38 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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