# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123034 | ezzzay | Fountain (eJOI20_fountain) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
bool vis[N];
int d[N],c[N];
vector<int>ans ;
vector<int>v[N];
int par[30][N];
int dst[N];
void dfs(int a){
for(auto b:v[a]){
dst[b]=dst[a]+c[a];
dfs(b);
}
}
signed main(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>d[i]>>c[i];
}
c[n+1]=1e9;
stack<pair<int,int>> st;
st.push({int(1e9), int(n+1)}) ;
for(int i=n;i>=1;i--){
while (!st.empty() && st.top().first <= d[i]) st.pop();
int p=st.top().ss;
v[p].pb(i);
par[0][i]=p;
st.push({d[i], i});
}
par[0][n+1]=n+1;
for(int i=1;i<19;i++){
for(int j=1;j<=n;j++){
par[i][j]=par[i-1][par[i-1][j]];
}
}
dfs(n+1);
while(q--){
int x,v;
cin>>x>>v;
for(int i=18;i>=0;i--){
int p=par[i][x];
if(dst[x] dst[p] ){
x=p;
}
}
}
}