Submission #1065138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065138		YassirSalama	Fish 2 (JOI22_fish2)	C++17	8 / 100	66 ms	53844 KiB

fish2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#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);
    }
}
signed 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
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17