Submission #1164896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164896		_Knyaz_	Fountain (eJOI20_fountain)	C++17	30 / 100	46 ms	4196 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<int> validReservoirs;

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);
    }

    // Compute prefix sums for valid reservoirs
    prefixSum[0] = 0;
    for (int i = 1; i <= N; i++) {
        prefixSum[i] = prefixSum[i - 1] + C[i];
    }
}

int findStoppingReservoir(int Ri, long long Vi) {
    // Binary search to find the first reservoir that accumulates at least Vi liters
    int L = Ri, R = N, answer = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        long long totalWater = prefixSum[mid] - prefixSum[Ri - 1];

        if (totalWater >= Vi) {
            answer = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    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: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40