제출 #965770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965770		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	310 ms	61712 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pp pair<int,int> 
#define ishowpeed ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int MXN = 2e5+5;
int anc[MXN][25],vals[MXN][25];
vector<int> edges[MXN];
int N,Q,D,C,R,V;
vector<pp> v;
void dfs(int u,int f,int depth=0){
    for(auto c:edges[u]){
        if(c == f) continue;
        anc[c][0] = u;
        vals[c][0] = v[c].S;
        dfs(c,u,depth+1);
    }
}
void inianc(){
    for(int i = N+1;i >=1;--i){
        for(int k = 1; k < 20;++k){
            anc[i][k] = anc[anc[i][k-1]][k-1];
            if(i == N+1) vals[i][k] = 1e10;
            else vals[i][k] = vals[anc[i][k-1]][k-1] + vals[i][k-1];
        }
    }
}
int search(int v,int cap){
    int temp = 0;
    for(int i = 19; i >=0;--i){
        if(cap > temp + vals[v][i]){
            // cout << v << ' ' << vals[v][i] << '\n';
            temp += vals[v][i];
            v = anc[v][i];
        }
    }
    return v;
}
signed main(){
    ishowpeed
    cin >> N >> Q;
    v.push_back({0,0});
    for(int i = 0; i < N;++i){
        cin >> D >> C;
        v.push_back({D,C});
    }
    v.push_back({1e10,1e10});
    vector<pp> deq;
    for(int i = 1; i <= N+1;++i){
        while(deq.size() && v[i].F > deq.back().F){
            int u = deq.back().S;
            edges[i].push_back(u);
            edges[u].push_back(i);
            deq.pop_back();
        }
        deq.push_back({v[i].F,i});
    }
    anc[N+1][0] = N+1;
    vals[N+1][0] = 1e10;
    dfs(N+1,N+1);
    inianc();
    while(Q--){
        cin >> R >> V;
        int ret = search(R,V);
        if(ret == N+1) cout << 0 << '\n';
        else cout << ret << '\n';
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40