Submission #1197889

#TimeUsernameProblemLanguageResultExecution timeMemory
1197889mishasimFountain (eJOI20_fountain)C++20
30 / 100
1575 ms3184 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' long long n,q,val,pos,currd; long long d[100005],v[100005],nextx[100005]; vector<int> vv; stack<int> st; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>q; for(int i = 1 ; i<=n ; i++){ cin>>d[i]>>v[i]; } for(int i = n ; i>=1 ; i--){ while(st.size()>0 && d[st.top()]<d[i]){ st.pop(); } if(st.size()==0)nextx[i] = 0; else nextx[i] = st.top(); st.push(i); } for(int i = 1 ; i<=q ; i++){ cin>>pos>>val; currd = 0; int j = pos; while(j<=n){ if(d[j]>currd){ currd = d[j]; val-=v[j]; if(val<=0){cout<<j<<endl;break;} } j = nextx[j]; if(j==0){cout<<0<<endl;val = 0;break;} } if(val>0)cout<<0<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...