This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <utility>
#include <cmath>
using namespace std;
typedef long long ll;
const int MXN = 1e5 + 10 ;
int cap[MXN] = {0};
int di[MXN] = {0};
int pscap[MXN] = {0};
vector<int> G[MXN];
pair<int, int> successor[20][MXN];
const int INF = 1e8 + 300;
int main(){
//faster io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, Q;
cin>>N>>Q;
for(int i=1; i<=N; i++) cin>>di[i]>>cap[i];
//themselves
for(int i=1; i<N; i++){
successor[0][i].first = i;
successor[0][i].second = cap[i];
}
//N + 1 nodes
stack<pair<int, int>> st;
for(int i=N; i>=1; i--){
if(st.empty()){
G[i].push_back(N+1);
successor[1][i].first = N+1;
successor[1][i].second = INF;
st.push(make_pair(di[i], i));
continue;
}
while((!st.empty()) && ((st.top().first)<di[i])){
st.pop();
}
if(st.empty()){
G[i].push_back(N+1);
successor[1][i].first = N+1;
successor[1][i].second = INF;
}
else{
G[i].push_back(st.top().second);
successor[1][i].first = st.top().second;
successor[1][i].second = cap[st.top().second] + cap[i];
}
st.push(make_pair(di[i], i));
}
// cout<<"hi";
// for(int i=1; i<=N; i++){
// cout<<successor[1][i].first<<" "<<successor[1][i].second<<"\n";
// }
//binary jumping matrix for successors
for(int i=2; i<20; i++){
for(int j=1; j<=N; j++){
successor[i][j].first = successor[i-1][successor[i-1][j].first].first;
if((successor[i-1][successor[i-1][j].first].second==INF) ||
(successor[i-1][j].second==INF)){
successor[i][j].second = INF;
continue;
}
successor[i][j].second = successor[i-1][j].second + successor[i-1][successor[i-1][j].first].second;
successor[i][j].second -= cap[successor[i-1][j].first];
}
}
// for(int j=1; j<20; j++){
// cout<<"j="<<j<<"\n";
// cout<<successor[j][5].first<<" "<<successor[j][5].second<<"\n";
// }
// cout<<"\n";
// for(int j=1; j<20; j++){
// cout<<"j="<<j<<"\n";
// cout<<successor[j][2].first<<" "<<successor[j][2].second<<"\n";
// }
while(Q--){
int R, V;
cin>>R>>V;
if(V<=cap[R]){
cout<<R<<"\n";
continue;
}
int a = R;
//binary search amongst R's successors
for(int i=19; i>=1; i--){
// cout<<a<<" ";
if(successor[i][a].second>=V){
continue;
}
if(successor[i][a].second<V){
// cout<<"hi";
V-=successor[i][a].second;
a = successor[i][a].first;
// cout<<"V="<<V<<" ";
}
}
// cout<<a<<" ";
a = successor[1][a].first;
// cout<<a<<"\n";
if(a==(N+1)) cout<<"0\n";
else cout<<a<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |