Submission #1235467

#TimeUsernameProblemLanguageResultExecution timeMemory
1235467em4ma2Fountain (eJOI20_fountain)C++20
0 / 100
10 ms3912 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; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...