#include<bits/stdc++.h>
using namespace std;
vector<long> dmt,cap;
vector<vector<int>> sgtf,sgtv;
int aux;
long query(long a,long b)
{
aux=0;
if(b<=sgtv[a][0]) return a;
else {while(b>sgtv[a][aux]&&sgtv[a][aux]!=*sgtv[a].end())
{
sgtv[a][aux++];
}
if(sgtv[a][aux]==*sgtv[a].end()) return sgtf[a][*prev(sgtf[a].end())];
else return sgtf[a][aux-1];
}
}
void solve()
{
long n,q;
cin>>n>>q;
dmt.assign(n+2,1e5+10);
cap.assign(n+1,1e5+10);
sgtf.resize(n+2,vector<int> (1,0));
sgtv.resize(n+2,vector<int> (1,0));
long a,b;
for(int i=1; i<=n; i++)
{
cin>>a>>b;
dmt[i]=a,cap[i]=b;
}
stack<long> pila;
pila.push(0);
for(int i=n; i>=1; i--)
{
//pila.push(i+1);
sgtv[i][0]=cap[i];
/*if(dmt[pila.top()]==0)
{
sgtf[i][0]=0, pila.pop();
}
else
{*/
/*if(dmt[i]<dmt[pila.top()]) sgtf[i][0]=pila.top();
else
{*/
while(dmt[i]>=dmt[pila.top()])
{
pila.pop();
}
//if(pila.empty())
//sgtf[i][0]=0;
//else
sgtf[i][0]=pila.top();
pila.push(i);
//}
//}
}
/*for(int i=1;i<=n;i++){
cout<<sgtf[i][0]<<" ----------- "<<sgtv[i][0]<<endl;
}*/
int s;
for(int i=1;i<=n;i++)
{
s=i;
while(s){
s=sgtf[s][0];
sgtf[i].push_back(sgtf[s][0]);
}
s=sgtv[i][0];
for(auto x:sgtf[i])
{
sgtv[i].push_back(s+sgtv[x][0]);
s+=sgtv[x][0];
}
}
while(q--)
{
cin>>a>>b;
cout<<query(a,b)<<endl;
}
}
int main()
{
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |