Submission #668011

#	Time	Username	Problem	Language	Result	Execution time	Memory
668011		haxorman	Fountain (eJOI20_fountain)	C++14	100 / 100	383 ms	50380 KiB

fountain

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

#define int long long

const int mxN = 2e5 + 7;

int sparse[20][mxN], dist[20][mxN], h[mxN];
pair<int,int> arr[mxN];
vector<pair<int,int>> graph[mxN];

void dfs(int u, int par, int weight) {
    sparse[0][u] = (par == -1 ? 0 : par);
    dist[0][u] = weight;
    h[u] = (par == -1 ? -1 : h[par]) + 1;
    
    for (int i = 1; i < 20; ++i) {
        sparse[i][u] = sparse[i - 1][sparse[i - 1][u]];
        dist[i][u] = dist[i - 1][u] + dist[i - 1][sparse[i - 1][u]];
    }

    for (auto p : graph[u]) {
        int v = p.first, w = p.second;
        dfs(v, u, w);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
    int n, q;
    cin >> n >> q;
    
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].first >> arr[i].second;
    }


    vector<int> st;
    for (int i = 1; i <= n; ++i) {
        while (st.size() && arr[i].first > arr[st.back()].first) {
            graph[i].push_back({st.back(), arr[st.back()].second});
            st.pop_back();
        }
        st.push_back(i);
    }

    while (st.size()) {
        graph[0].push_back({st.back(), arr[st.back()].second});
        st.pop_back();
    }
    dfs(0, -1, 0);

    while (q--) {
        int ind, val;
        cin >> ind >> val;

        for (int i = 19; i >= 0 && val; --i) {
            if (dist[i][ind] && dist[i][ind] < val) {
                val -= dist[i][ind];
                ind = sparse[i][ind];
            }
        }
        cout << ind << "\n";
    }
}

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