oj.uz

Submission #1065138

# Submission time Handle Problem Language Result Execution time Memory
1065138 2024-08-19T00:21:15 Z YassirSalama Fish 2 (JOI22_fish2) C++17
8 / 100
 66 ms 53844 KB 
#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.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52060 KB Output is correct
2 Correct 48 ms 52876 KB Output is correct
3 Correct 42 ms 53076 KB Output is correct
4 Correct 49 ms 53328 KB Output is correct
5 Correct 42 ms 53084 KB Output is correct
6 Correct 59 ms 53844 KB Output is correct
7 Correct 46 ms 53084 KB Output is correct
8 Correct 60 ms 53844 KB Output is correct
9 Correct 52 ms 53072 KB Output is correct
10 Correct 66 ms 53460 KB Output is correct
11 Correct 41 ms 52932 KB Output is correct
12 Correct 40 ms 53076 KB Output is correct
13 Correct 40 ms 53076 KB Output is correct
14 Correct 50 ms 53328 KB Output is correct
15 Correct 56 ms 53332 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52060 KB Output is correct
2 Correct 48 ms 52876 KB Output is correct
3 Correct 42 ms 53076 KB Output is correct
4 Correct 49 ms 53328 KB Output is correct
5 Correct 42 ms 53084 KB Output is correct
6 Correct 59 ms 53844 KB Output is correct
7 Correct 46 ms 53084 KB Output is correct
8 Correct 60 ms 53844 KB Output is correct
9 Correct 52 ms 53072 KB Output is correct
10 Correct 66 ms 53460 KB Output is correct
11 Correct 41 ms 52932 KB Output is correct
12 Correct 40 ms 53076 KB Output is correct
13 Correct 40 ms 53076 KB Output is correct
14 Correct 50 ms 53328 KB Output is correct
15 Correct 56 ms 53332 KB Output is correct
16 Incorrect 22 ms 52060 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52060 KB Output is correct
2 Correct 48 ms 52876 KB Output is correct
3 Correct 42 ms 53076 KB Output is correct
4 Correct 49 ms 53328 KB Output is correct
5 Correct 42 ms 53084 KB Output is correct
6 Correct 59 ms 53844 KB Output is correct
7 Correct 46 ms 53084 KB Output is correct
8 Correct 60 ms 53844 KB Output is correct
9 Correct 52 ms 53072 KB Output is correct
10 Correct 66 ms 53460 KB Output is correct
11 Correct 41 ms 52932 KB Output is correct
12 Correct 40 ms 53076 KB Output is correct
13 Correct 40 ms 53076 KB Output is correct
14 Correct 50 ms 53328 KB Output is correct
15 Correct 56 ms 53332 KB Output is correct
16 Incorrect 22 ms 52060 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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