Submission #1182292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182292		meicris	Fountain (eJOI20_fountain)	C++17	0 / 100	23 ms	13072 KiB

fountain

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int N, Q;
vector<int> D, C;
vector<vector<int>> jump;

void preprocess() {
    vector<int> next(N, -1);
    stack<int> s;
    for (int i = N - 1; i >= 0; --i) {
        while (!s.empty() && D[i] >= D[s.top()]) {
            s.pop();
        }
        if (!s.empty()) next[i] = s.top();
        s.push(i);
    }

    int LOG = 20;
    jump.assign(N, vector<int>(LOG, -1));
    for (int i = 0; i < N; ++i)
        jump[i][0] = next[i];

    for (int j = 1; j < LOG; ++j) {
        for (int i = 0; i < N; ++i) {
            int mid = jump[i][j - 1];
            if (mid != -1)
                jump[i][j] = jump[mid][j - 1];
        }
    }
}

int pour(int idx, int V, int idj, int in) {
    while (true) {
        if (V <= C[idx]) return idx + 1;
        if(jump[in][idj]<0){
            return 0;
        }
        int n=jump[idx][idj];
        V -= C[idx];
        return pour(n,V,idx,in);
    }
}

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

    cin >> N >> Q;
    D.resize(N);
    C.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> D[i] >> C[i];

    preprocess();

    while (Q--) {
        int R, V;
        cin >> R >> V;
        cout << pour(R - 1, V, 0, R-1) << '\n';
    }
    return 0;
}

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