Submission #866514

#	Time	Username	Problem	Language	Result	Execution time	Memory
866514		hanifchdn	Fountain (eJOI20_fountain)	C++17	100 / 100	235 ms	40016 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

ll d[N], a[N];
pair<int, ll> par[N][20];
stack<pair<int, ll>> s;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> d[i] >> a[i];
    a[0] = 2e9;
    s.push({0, 2e9});
    for (int i = n; i >= 1; i--) {
        while (d[i] >= s.top().se) s.pop();
        par[i][0] = {s.top().fi, a[s.top().fi]};
        for (int j = 1; j < 20; j++) par[i][j] = {par[par[i][j - 1].fi][j - 1].fi, par[par[i][j - 1].fi][j - 1].se + par[i][j - 1].se};
        s.push({i, d[i]});
    }
    while (q--) {
        int r;
        ll v;
        cin >> r >> v;
        v -= a[r];
        if (v <= 0) {
            cout << r << "\n";
            continue;
        }
        for (int i = 19; i >= 0; i--) {
            if (par[r][i].se < v) {
                v -= par[r][i].se;
                r = par[r][i].fi;
            }
        }
        cout << par[r][0].fi << "\n";
    }
}  

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