Submission #1190130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190130		lokesh0110	Fountain (eJOI20_fountain)	C++17	100 / 100	128 ms	24248 KiB

fountain

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

const int MAXN = 100000;
const int LOG = 18;  // since 2^17 = 131072 > 100000

int up[MAXN+1][LOG];
ll sumCap[MAXN+1][LOG];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<int> D(N+1), C(N+1);
    for(int i = 1; i <= N; i++){
        cin >> D[i] >> C[i];
    }

    // parent[i] = index of the next reservoir below i with strictly larger diameter (or 0)
    vector<int> parent(N+1, 0);
    stack<int> st;
    for(int i = N; i >= 1; i--){
        while(!st.empty() && D[st.top()] <= D[i]) {
            st.pop();
        }
        parent[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }

    // Binary lifting tables:
    // up[i][k] = the 2^k-th ancestor of i along the "next-greater" chain
    // sumCap[i][k] = sum of capacities of the 2^k nodes starting at i along that chain
    for(int i = 1; i <= N; i++){
        up[i][0]      = parent[i];
        sumCap[i][0]  = C[i];
    }
    // ensure up[0][*] = 0, sumCap[0][*] = 0 by static initialization

    for(int k = 1; k < LOG; k++){
        for(int i = 1; i <= N; i++){
            int p = up[i][k-1];
            up[i][k] = (p == 0 ? 0 : up[p][k-1]);
            sumCap[i][k] = sumCap[i][k-1]
                         + (p == 0 ? 0LL : sumCap[p][k-1]);
        }
    }

    // Answer each query independently
    while(Q--){
        int R;
        ll V;
        cin >> R >> V;

        ll rem = V;
        int curr = R;

        // Jump as far as we can while the total capacity of the jumped-over
        // reservoirs is still less than the remaining water.
        for(int k = LOG - 1; k >= 0; k--){
            if(curr != 0 && up[curr][k] != 0 && sumCap[curr][k] < rem){
                rem  -= sumCap[curr][k];
                curr  = up[curr][k];
            }
        }

        // Now curr is the highest node we can reach without exceeding rem.
        // The next reservoir to fill is curr itself:
        int answer = 0;
        if(curr != 0 && C[curr] >= rem) {
            answer = curr;
        } else {
            // Either curr==0 (we fell off) or its capacity < rem.
            // In both cases, the water flows to waterways.
            answer = 0;
        }

        cout << answer << "\n";
    }

    return 0;
}

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