Submission #1245282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245282		kchu_z	Fountain (eJOI20_fountain)	C++20	100 / 100	606 ms	39892 KiB

fountain

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

long long n, q, diameter[100001], capacity[100001], parent[100001], dp[100001][20];
long long dp_sum[100001][20];

bool visited[100001][20], visited_sum[100001][20];

long long lift(long long vertice, long long lg) {
    if (lg == 0) return parent[vertice];

    if (visited[vertice][lg]) return dp[vertice][lg];
    visited[vertice][lg] = 1;

    return dp[vertice][lg] = lift(lift(vertice, lg - 1), lg - 1);
}

long long sum(long long vertice, long long lg) {
    if (lg == 0) return capacity[vertice];

    if (visited_sum[vertice][lg]) return dp_sum[vertice][lg];
    visited_sum[vertice][lg] = 1;

    return dp_sum[vertice][lg] = sum(vertice, lg - 1) + sum(lift(vertice, lg - 1), lg - 1);
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    stack <long long> st;

    for (long long i = 0; i < n; i++) {
        cin >> diameter[i] >> capacity[i];
    }

    diameter[n] = 1e9 + 1;
    capacity[n] = 1e9;

    for (long long i = 0; i <= n; i++) {
        while (st.size() && diameter[st.top()] < diameter[i]) {
            parent[st.top()] = i;
            st.pop();
        }

        st.push(i);
    }

    parent[n] = n;

    while (q--) {
        long long vertice, volume;
        cin >> vertice >> volume;
        vertice--;

        for (long long mask = 20; mask >= 0; mask--) {
            if (sum(vertice, mask) >= volume) continue;

            volume -= sum(vertice, mask);
            vertice = lift(vertice, mask);
        }

        cout << (vertice + 1) % (n + 1) << endl;
    }

    return 0;

}

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