Submission #597130

#	Time	Username	Problem	Language	Result	Execution time	Memory
597130		Kipras	Fountain (eJOI20_fountain)	C++17	100 / 100	453 ms	38400 KiB

fountain

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxN = 1e5+10;
const ll maxLog = 25;

ll adj[maxN];
vector<ll> adjR[maxN];
ll n, q;
vector<ll> d, c;
ll up[maxN][maxLog];
ll dep[maxN];

void readValues(){

    cin>>n>>q;

    d.push_back(0);
    c.push_back(0);

    for(int i = 0; i < n; i++){
        ll aa, bb;
        cin>>aa>>bb;
        d.push_back(aa);
        c.push_back(bb);
    }

}

void constructTree(){

    deque<ll> waiting;

    waiting.push_back(1);

    for(int i = 2; i <= n; i++){
        while(waiting.size()>0&&d[waiting.back()]<d[i]){
            adj[waiting.back()]=i;
            adjR[i].push_back(waiting.back());
            waiting.pop_back();
        }
        waiting.push_back(i);
    }

    for(auto i : waiting){
        adj[i]=0;
        adjR[0].push_back(i);
    }

}

void optimiseTree(){

    up[0][0]=0;
    for(int i = 1; i <= n; i++){
        up[i][0]=adj[i];
    }

    for(int i = 1; i < maxLog; i++){
        for(int x = 1; x <= n; x++){
            up[x][i]=up[up[x][i-1]][i-1];
        }
    }

}

void getDepth(ll v, ll depth){

    dep[v]=depth+c[v];

    for(auto i : adjR[v]){

        getDepth(i, dep[v]);

    }

}

ll goUp(ll v, ll x){
    for(int i = 0; i < maxLog; i++){
        if(x&(1<<i)){
            v=up[v][i];
        }
    }
    return v;
}

ll solve(ll ind, ll cFill){

    //ind = up[ind][0];

    //cout<<dep[ind]<<" a "<<cFill<<endl;

    if(dep[ind]<cFill)return 0;

    ll a=ind;

    for(int i = maxLog-1; i >= 0; i--){

        ll b = goUp(a, 1<<i);

        if(dep[b]<=dep[ind]-cFill)continue;
        else a=b;

    }

    return a;

}

void readQueries(){

    for(int i = 0; i < q; i++){
        ll ind, cFill;
        cin>>ind>>cFill;

        cout<<solve(ind, cFill)<<"\n";

    }

}

int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    readValues();

    constructTree();

    optimiseTree();

    d[0]=0;
    c[0]=0;
    dep[0]=0;

    getDepth(0, 0);

    readQueries();

    return 0;
}

/*

6 1
4 10
6 8
3 5
4 14
10 9
4 20
1 25

*/

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