Submission #1235467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235467		em4ma2	Fountain (eJOI20_fountain)	C++20	0 / 100	10 ms	3912 KiB

fountain

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl '\n'
#define pb push_back
 
const int off = 1<<19;
const int mxsz = 2e5+4;
const ll inf = 1e9+4;
const int pz = 30;
 
ll par[mxsz];
ll an[pz][mxsz];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n,q;
    cin>>n>>q;
    ll d[n],c[n];
    for (int i=0;i<n;i++){
        cin>>d[i]>>c[i];
    }
    vector<int>ng(n);
    stack<pair<int,int>>st;
    st.push({n,inf});
    for (int i=n-1;i>=0;i--){
        while (!st.empty() && st.top().second<=d[i]){
            st.pop();
        }
        if (!st.empty()){
            ng[i]=st.top().first;
        }else{
            ng[i]=-1;
        }
        st.push({i,d[i]});
    }
    // for (int i=0;i<n;i++){
    //     cout<<ng[i]<<" ";
    // }cout<<endl;
    for (ll i=0;i<n;i++){
        an[0][i]=ng[i];
    }
    for (int i=0;i<=n;i++){
        an[i][n]=-1;
    }
    for (ll j=1;j<pz;j++){
        for (ll i=0;i<n;i++){
            if (an[j-1][i]!=-1)
                an[j][i]=an[j-1][an[j-1][i]];
            else
                an[j][i]=-1;
        }
    }
    // for (int i=0;i<n;i++){
    //     for (int j=0;j<3;j++){
    //         cout<<an[j][i]<<" ";
    //     }cout<<endl;
    // }
    while (q--){
        ll i,k;
        cin>>i>>k;
        i--;
        while (k>c[i]){
            k-=c[i];
            ll kl=i;
            for (ll b=pz-1;b>=0;b--){
                ll j=an[b][kl];
                if (j!=-1 && c[j]<k){
                    kl=j;
                }
            }
            i=an[0][i];
            if (i==-1)break;
        }
        cout<<i+1<<endl;
    }
 
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40