Submission #1164892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164892		_Knyaz_	Fountain (eJOI20_fountain)	C++17	30 / 100	1596 ms	3668 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];

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

int findStoppingReservoir(int Ri, long long Vi) {
    long long total = 0;
    int current = Ri;
    
    while (current != 0 && total + C[current] < Vi) {
        total += C[current];
        current = nextReservoir[current];  // Move to next valid reservoir
    }
    return current;
}

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