Submission #1190127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190127		lokesh0110	Fountain (eJOI20_fountain)	C++17	0 / 100	56 ms	9284 KiB

fountain

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

const int MAXN = 1e5 + 5;
const int LOG = 20;

int n, q;
int D[MAXN], C[MAXN], nxt[MAXN];
int up[MAXN][LOG];

void build_next_larger() {
    stack<int> st;
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && D[st.top()] <= D[i]) st.pop();
        nxt[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }
}

void build_lifting() {
    for (int i = 1; i <= n; ++i)
        up[i][0] = nxt[i];
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (up[i][j-1] != 0)
                up[i][j] = up[up[i][j-1]][j-1];
            else
                up[i][j] = 0;
        }
    }
}

int simulate(int r, int v) {
    while (v > C[r]) {
        v -= C[r];
        int next = r;
        for (int j = LOG - 1; j >= 0; --j) {
            int to = up[next][j];
            if (to && C[to] < v) next = to;
        }
        r = nxt[next];
        if (r == 0) return 0;
    }
    return r;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> D[i] >> C[i];
    }

    build_next_larger();
    build_lifting();

    while (q--) {
        int r, v;
        cin >> r >> v;
        cout << simulate(r, v) << '\n';
    }

    return 0;
}

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