#include<bits/stdc++.h>
using namespace std;
const int LG=1e10;
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+1,1e5+10);
cap.assign(n+1,1e5+10);
sgtf.resize(n+1,vector<int> (20,0));
sgtv.resize(n+1,vector<int> (20,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--)
{
sgtv[i][0]=cap[i];
while(dmt[i]>=dmt[pila.top()])
{
pila.pop();
}
sgtf[i][0]=pila.top();
pila.push(i);
}
for(int j=1; j<20; j++)
for(int i=1; i<n+1; i++)
{
int parent=sgtf[i][j-1];
sgtv[i][j]=sgtv[i][j-1]+sgtv[parent][j-1];
sgtf[i][j]=sgtf[parent][j-1];
}
/*for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
cout<<sgtv[i][j]<<" ";
}
cout<<endl;
}*/
while(q--)
{
cin>>a>>b;
cout<<query(a,b)<<endl;
}
}
int main()
{
solve();
}
Compilation message (stderr)
fountain.cpp:3:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
3 | const int LG=1e10;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |