Submission #1275294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275294		__ugur__	Fountain (eJOI20_fountain)	C++20	30 / 100	1595 ms	1720 KiB

fountain

#include <bits/stdc++.h>

using namespace std;


vector<int> diameters(100001);      // D
vector<int> capacities(100001);     // C
vector<int> next_drain(100001, -1);     // next higher, min D (like pointer)

int stack_mem[100002];
int ptr = 0;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;
    //diameters = vector<int>(N+1);
    //capacities = vector<int>(N+1);
    //next_drain = vector<int>(N+1, -1);
    
    for(int i=1; i<=N; i++) {
        int d, c;
        cin >> d >> c;
        diameters[i] = d;
        capacities[i] = c;

        while(ptr && diameters[stack_mem[ptr-1]] < d)
            next_drain[stack_mem[--ptr]] = i;

        if(diameters[i-1] < d)
            next_drain[i-1] = i;
        else
            stack_mem[ptr++] = i-1;
    }

    while(Q--) {
        int start, vol;
        cin >> start >> vol;
        while(start >= 0) {
            vol -= capacities[start];
            if(vol < 1)
                break;
            start = next_drain[start];
        }
        if(start == -1)
            cout << "0\n";
        else
            cout << start << '\n';
    }
    
    return 0;
}
//6 5 4 10 6 8 3 5 4 14 10 9 4 20 1 25 6 30 5 8 3 13 2 8

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