oj.uz

Submission #592118

# Submission time Handle Problem Language Result Execution time Memory
592118 2022-07-08T14:13:35 Z Iwanttobreakfree Fountain (eJOI20_fountain) C++
100 / 100
 717 ms 49528 KB 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int bin_lift(int a,vector<vector<pair<int,long long>>>& p,int w){
    for(int i=17;i>=0;i--){
        if(p[a][i].second<w){
            w-=p[a][i].second;
            a=p[a][i].first;
        }
    }
    //cout<<w<<' ';
    return a;
}
void dfs(int a,int par,int w,vector<vector<pair<int,int>>>& g,vector<vector<pair<int,long long>>>& p){
    //cout<<a<<' '<<par<<'\n';
    p[a][0]={par,w};
    for(int i=1;i<18;i++)p[a][i]={p[p[a][i-1].first][i-1].first,p[a][i-1].second+p[p[a][i-1].first][i-1].second};
    for(auto x:g[a]){
        dfs(x.first,a,x.second,g,p);
    }
}
int main(){
    int n,q,x,v;
    cin>>n>>q;
    vector<pair<int,int>> f(n);
    vector<vector<pair<int,int>>> g(n+1,vector<pair<int,int>>());
    vector<vector<pair<int,long long>>> par(n+1,vector<pair<int,long long>>(18));
    for(int i=0;i<n;i++){
        cin>>x>>v;
        f[i]={x,v};
    }
    stack<pair<int,int>> st;
    st.push({1e9+7,0});
    for(int i=n-1;i>=0;i--){
        while(st.top().first<=f[i].first)st.pop();
        g[st.top().second].push_back({i+1,f[i].second});

        st.push({f[i].first,i+1});
    }
    dfs(0,0,1e9+7,g,par);
    /*for(int i=0;i<=n;i++){
        cout<<i<<'\n';
        for(int j=0;j<18;j++)cout<<par[i][j].first<<' ';
        cout<<endl;
    }*/
    while(q--){
        cin>>x>>v;
        cout<<bin_lift(x,par,v)<<'\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 5 ms 780 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 45700 KB Output is correct
2 Correct 537 ms 42756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 5 ms 780 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 475 ms 45700 KB Output is correct
9 Correct 537 ms 42756 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 262 ms 23756 KB Output is correct
12 Correct 717 ms 49528 KB Output is correct
13 Correct 605 ms 43340 KB Output is correct
14 Correct 485 ms 41748 KB Output is correct
15 Correct 462 ms 40912 KB Output is correct