Submission #1256454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256454		random_name	Fountain (eJOI20_fountain)	C++20	100 / 100	308 ms	22928 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<pair<pair<ll, ll>, vector<ll>>> tree;
vector<vector<ll>> which;
vector<pair<ll, ll>> where;

ll count_childs(vector<ll>* A, vector<vector<ll>>* B, ll n){
    ll max_child = 0;
    for(ll edge: (*B)[n]){
        max_child = max(max_child, count_childs(A, B, edge));
    }

    (*A)[n] = max_child + 1;

    return max_child + 1;
}

ll querry(pair<ll, ll> n, ll w){
    if(tree[n.first].second[n.second] < w){
        if(tree[n.first].first.first == -1){
            return 0;
        }

        return querry(tree[n.first].first, w - tree[n.first].second[n.second]);
    }

    return which[n.first][upper_bound(tree[n.first].second.begin(), tree[n.first].second.end(), tree[n.first].second[n.second] - w) - tree[n.first].second.begin()];
}


int main(){
    ll n, q;
    cin >> n >> q;
    vector<pair<ll, ll>> A(n);
    for(ll i = 0; i < n; i++){
        cin >> A[i].first >> A[i].second;
    }

    vector<ll> br(n, -1);
    stack<ll> que;
    for(ll i = 0; i < n; i++){
        while(!que.empty() && A[que.top()].first < A[i].first){
            br[que.top()] = i;
            que.pop();
        }

        que.push(i);
    }

    vector<vector<ll>> childs(n+1);

    for(ll i = 0; i < n; i++){
        if(br[i] != -1)
            childs[br[i]+1].push_back(i+1);

        else
            childs[0].push_back(i+1);
    }

    vector<ll> child_counts(n+1);

    count_childs(&child_counts, &childs, 0);

    tree.push_back({{-1, -1}, vector<ll>(1, 0)});
    which.push_back(vector<ll>(1, 0));

    where.resize(n+1);

    while(!que.empty()) que.pop();
    que.push(0);

    while(!que.empty()){
        ll c = que.top();
        que.pop();


        ll max_child = -1;
        for(ll child: childs[c]){
            if(max_child == -1 || child_counts[child] > child_counts[max_child]){
                max_child = child;
            }
        }

        if(max_child == -1){
            continue;
        }


        for(ll child: childs[c]){
            if(child == max_child)
                continue;

            que.push(child);

            where[child] = {tree.size(), 0};
            tree.push_back({where[c], {A[child-1].second}});
            which.push_back({{child}});
        }

        que.push(max_child);
        // cout << c << endl;
        where[max_child] = {where[c].first, tree[where[c].first].second.size()};
        // cout << tree.size() << ' ' << where[c].first << ' ' << max_child << endl;
        tree[where[c].first].second.push_back(A[max_child-1].second + tree[where[c].first].second.back());
        which[where[c].first].push_back(max_child);
    }

    while(q--){
        ll x, y;
        cin >> x >> y;
        
        cout << querry(where[x], y) << '\n';
    }
}

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