Submission #1137073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137073		SulA	Fountain (eJOI20_fountain)	C++20	100 / 100	260 ms	26356 KiB

fountain

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ulong unsigned long long
#define uint unsigned int

int par[100'001][20];
long long sum[100'001][20];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n,q; cin>>n>>q;
    int d[n+1], c[n+1];
    for (int i = 0; i < n; cin>>d[i]>>c[i++]);
    d[n] = c[n] = 1e9;
    vector<int> st { n };
    par[n][0] = n;
    sum[n][0] = c[n];
    for (int i = n-1; i >= 0; i--) {
        while (d[st.back()] <= d[i])
            st.pop_back();
        par[i][0] = st.back();
        sum[i][0] = c[i];
        st.push_back(i);
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= n; i++) {
            par[i][j] = par[par[i][j-1]][j-1];
            sum[i][j] = sum[i][j-1] + sum[par[i][j-1]][j-1];
        }
    }
    while (q--) {
        int r,v; cin>>r>>v;
        r--;
        for (int j = 19; j >= 0; j--) {
            if (sum[r][j] < v) {
                v -= sum[r][j];
                r = par[r][j];
            }
        }
        cout << (r == n ? 0 : r+1) << '\n';
    }
}

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