oj.uz

Submission #446092

# Submission time Handle Problem Language Result Execution time Memory
446092 2021-07-20T21:59:52 Z Ronin13 Fountain (eJOI20_fountain) C++14
0 / 100
 1500 ms 14692 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define epb emplace_back
#define pb push_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

void solve(){
    int n;cin>>n;
    int q;cin>>q;
    ll c[n+2],d[n+2];
    for(int i=1;i<=n;i++){
        cin>>d[i]>>c[i];
    }
    stack<ll>st;
    st.push(n+1);
    d[n+1]=linf;


    int next[n+2][22];

    next[n+1][0]=n+1;
    int par[n+2];
    for(int i=1;i<=n+1;i++){
        par[i]=0;
    }
    ll pref[n+2];
    pref[0]=0;
    pref[n+1]=linf;

    for(int i=n;i>=1;i--){
        while(true){
            if(st.empty())break;
            int ind=st.top();
            if(d[ind]>d[i]){
                next[i][0]=ind;
                par[ind]=i;
                break;
            }
            else st.pop();
        }
        st.push(i);
    }

    for(int i=1;i<=n;i++){
        pref[i]=pref[par[i]]+c[i];
    }
    for(int j=1;j<=21;j++){
        for(int i=1;i<=n+1;i++){
            next[i][j]=next[next[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=21;j++){
            cerr<<next[i][j]<<' ';
        }
        cerr<<"\n";
    }

    while(q--){
        int ves;ll l;
        cin>>ves>>l;
        l+=pref[par[ves]];
        int cur=ves;
        if(pref[cur]>=l){
            cout<<cur<<"\n";
            continue;
        }
        for(int i=21;i>=0;i--){
            int nex=next[cur][i];
            if(pref[nex]<=l)cur=nex;

        }
        cout<<next[cur][0]%(n+1)<<"\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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