Submission #1238892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238892		em4ma2	Fountain (eJOI20_fountain)	C++20	100 / 100	211 ms	52288 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;
 
struct anc{
    ll r,c;
};

ll par[mxsz];
anc 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+1],c[n+1];
    for (int i=1;i<=n;i++){
        cin>>d[i]>>c[i];
    }
    vector<anc>ng(n+1);
    stack<int>st;
    for (int i=n;i>=1;i--){
        while (!st.empty() && d[st.top()]<=d[i]){
            st.pop();
        }
        if (!st.empty()){
            ng[i]={st.top(),c[i]};
        }else{
            ng[i]={0,c[i]};
        }
        st.push(i);
    }
    for (ll i=1;i<=n;i++){
        an[0][i]=ng[i];
    }
    for (ll j=1;j<pz;j++){
        for (ll i=1;i<=n;i++){
            an[j][i].r=an[j-1][an[j-1][i].r].r;
            an[j][i].c=an[j-1][an[j-1][i].r].c+an[j-1][i].c;
        }
    }
    while (q--){
        ll i,k;
        cin>>i>>k;
        for (int b=pz-1;b>=0;b--){
            if (k-an[b][i].c>0){
                k-=an[b][i].c;
                i=an[b][i].r;
            }
        }
        cout<<i<<endl;
    }
 
    return 0;
}

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