//unfin
#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
pair<int,int> go[200005][20];
int par[100005];
int main(){
int n,q;
cin>>n>>q;
int d[n+10];
int c[n+10];
for(int i=1; i<=n; i++){
cin>>d[i];
cin>>c[i];
}
d[n+1]=INT_MAX;
d[0]=INT_MAX;
stack<int> s;
s.push(n+1);
for(int i=n; i>=1; i--){
while(d[i]>=d[s.top()]){
s.pop();
}
go[i][0].s=s.top();
par[s.top()]=i;
go[i][0].f=c[i];
s.push(i);
}
for(int i=1; i<20; i++){
for(int ii=1; ii<200005; ii++){
go[ii][i].s=INT_MAX;
}
}
for(int i=1; i<20; i++){
for(int ii=0; ii<200005; ii++){
go[ii][i].f=go[go[ii][i-1].s][i-1].f+go[ii][i-1].f;
go[ii][i].s=go[go[ii][i-1].s][i-1].s;
if(ii>n){
go[ii][i].s=n+1;
}
if(ii<50){
// cout<<ii<<" "<<i<<" "<<go[ii][i].f<<" "<<go[ii][i].s<<endl;
}
}
}
for(int i=1; i<=q; i++){
int x,y;
cin>>x>>y;
int j=19;
int st=x;
while(true){
if(j==0 && y<=go[st][j].f){
cout<<st<<endl;
break;
}
while(y<go[st][j].f && j>0){
j--;
}
y-=go[st][j].f;
// cout<<y<<" y"<<endl;
//cout<<j<<" "<<go[st][j].s<<" "<<go[st][j].f<<endl;
//cout<<st<<" "<<j<<endl;
// cout<<go[go[st][i-1].s][j-1].s<<"bruh "<<endl;
if(y<=0){
cout<<par[go[st][j].s]<<endl;
break;
}
//if()
if(go[st][j].f==0){
cout<<"0"<<endl;
break;
}
st=go[st][j].s;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
31560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
523 ms |
36700 KB |
Output is correct |
| 2 |
Correct |
526 ms |
37044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
31560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
