Submission #1238892

#TimeUsernameProblemLanguageResultExecution timeMemory
1238892em4ma2Fountain (eJOI20_fountain)C++20
100 / 100
211 ms52288 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...