Submission #1309535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309535		zadniprovska	Fountain (eJOI20_fountain)	C++20	100 / 100	471 ms	44648 KiB

fountain

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
 
const ll DIM = 1e5 + 7;
const ll INF = 1e9;
const ll mod = 998244353;
const ll maxlog = 20;
const ll bsize = 350;

ll d[DIM], c[DIM], p[DIM][maxlog], s[DIM][maxlog];
bool flag[DIM];
vector<ll> a[DIM];

void dfs (ll v) {

    s[v][0] = c[v];
    for (int i=1; i<maxlog; i++) {
        p[v][i] = p[p[v][i-1]][i-1];

        s[v][i] = s[v][i-1] + s[p[v][i-1]][i-1];
    }


    for (auto to : a[v]) {
        p[to][0] = v;
        dfs(to);
    }

}

void solve() {

    ll n, nq;
    cin >> n >> nq;

    for (int i=1; i<=n; i++) {
        cin >> d[i] >> c[i];

        flag[i] = 1;
    }
    c[0] = INF;

    stack<ll> st;
    for (int i=1; i<=n; i++) {
        
        while (!st.empty() && d[st.top()] < d[i]) {
            a[i].pb(st.top());

            flag[st.top()] = 0;

            st.pop();
        }

        st.push(i);

    }

    for (int i=1; i<=n; i++) {
        if (flag[i]) {
            a[0].pb(i);
        }
    }

    dfs(0);

    /*for (int i=0; i<=n; i++) {

        cout << "/ " << i << endl;
        for (int j=0; j<maxlog; j++) {

            cout << p[i][j] << " ";

        }
        cout << endl;
        for (int j=0; j<maxlog; j++) {
            cout << s[i][j] << " ";
        }
        cout << endl;

    }*/

    for (int t=1; t<=nq; t++) {

        ll r, vol;
        cin >> r >> vol;

        ll up = 0, v = r;
        for (int i=maxlog-1; i>=0; i--) {

            if (vol >= s[v][i]) {
                vol -= s[v][i];
                up += (1 << i);

                v = p[v][i];
            }

        }
        if (vol > 0) {
            cout << v << endl;
            continue;
        }

        up--; v = r;
        for (int i=maxlog-1; i>=0; i--) {

            if (up >= (1 << i)) {
                up -= (1 << i);
                v = p[v][i];
            }

        }

        cout << v << endl;

    }



}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("atlarge.in", "r", stdin);
    //freopen("atlarge.out", "w", stdout);
 
    int ntest = 1;
    //cin >> ntest;
    while (ntest--) {
        solve();
    }
    return 0;
 
}
;

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