oj.uz

Submission #597130

# Submission time Handle Problem Language Result Execution time Memory
597130 2022-07-15T14:33:37 Z Kipras Fountain (eJOI20_fountain) C++17
100 / 100
 453 ms 38400 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2828 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2960 KB Output is correct
6 Correct 4 ms 2960 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 34364 KB Output is correct
2 Correct 365 ms 32032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2828 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2960 KB Output is correct
6 Correct 4 ms 2960 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 299 ms 34364 KB Output is correct
9 Correct 365 ms 32032 KB Output is correct
10 Correct 4 ms 2900 KB Output is correct
11 Correct 162 ms 19260 KB Output is correct
12 Correct 453 ms 38400 KB Output is correct
13 Correct 335 ms 33280 KB Output is correct
14 Correct 323 ms 31512 KB Output is correct
15 Correct 298 ms 31640 KB Output is correct