Submission #1164894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164894		_Knyaz_	Fountain (eJOI20_fountain)	C++17	30 / 100	1593 ms	3672 KiB

fountain

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

const int MAXN = 1e5 + 5;

long long N, Q, D[MAXN], C[MAXN], nextReservoir[MAXN], prefixSum[MAXN];
vector<pair<long long, long long>> Fountain;

void preprocess() {
    stack<int> s;
    for (int i = N; i >= 1; --i) {
        while (!s.empty() && D[s.top()] <= D[i]) {
            s.pop();
        }
        nextReservoir[i] = s.empty() ? 0 : s.top();
        s.push(i);
        prefixSum[i] = C[i] + (nextReservoir[i] ? prefixSum[nextReservoir[i]] : 0);
    }
}

int findStoppingReservoir(int Ri, long long Vi) {
    while (Ri != 0 && Vi > 0) {
        if (Vi <= C[Ri]) return Ri;
        Vi -= C[Ri];
        Ri = nextReservoir[Ri];
    }
    return 0;
}

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

    preprocess();  // Precompute overflow paths and prefix sums

    while (Q--) {
        int Ri;
        long long Vi;
        cin >> Ri >> Vi;
        cout << findStoppingReservoir(Ri, Vi) << '\n';
    }

    return 0;
}

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