| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1183707 | gabyferaq | Fountain (eJOI20_fountain) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
vector<long> dmt,cap;
vector<vector<long>> sgtf,sgtv;
long aux;
long query(long a,long b)
{
aux=sgtv[a].size()-2;
if(b<=sgtv[a][0]) return a;
else {
while(sgtv[a][aux]>b)
{
sgtv[a][aux--];
}
return sgtf[a][aux];
}
}
void solve()
{
long n,q;
cin>>n>>q;
dmt.assign(n+1,1e5+1);
cap.assign(n+1,1e5+1);
sgtf.resize(n+1,vector<long> (1,0));
sgtv.resize(n+1,vector<long> (1,0));
long a,b;
for(long i=1; i<=n; i++)
{
cin>>a>>b;
dmt[i]=a,cap[i]=b;
}
stack<long> pila;
pila.push(0);
for(long 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);
}
long s;
for(long i=1;i<=n;i++)
{
s=sgtf[i][0];
while(s>0)
{
sgtf[i].push_back(sgtf[s][0]);
s=sgtf[s][0];
}
s=sgtv[i][0];
for(auto x:sgtf[i])
{
if(s+sgtv[x][0]==s)
sgtv[i].push_back(0);
else sgtv[i].push_back(s+sgtv[x][0]);
s+=sgtv[x][0];
}
}
while(q--)
{
cin>>a>>b;
cout<<query(a,b)<<endl;
}
}
long main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}