Submission #642842

#	Time	Username	Problem	Language	Result	Execution time	Memory
642842		bonk	Fountain (eJOI20_fountain)	C++14	30 / 100	4 ms	980 KiB

fountain

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e3;
const int LOG = 18;
vector<ll>d(N + 2), a(N + 2);
vector<ll>adj[N + 2];
ll pref[N + 2][18], p[N + 2];
int up[N + 2][18];

void dfs(int prev, int cur){
    for(auto &nxt: adj[cur]){
        if(nxt == prev) continue;
        up[nxt][0] = cur; 
        pref[nxt][0] = a[nxt];
        for(int i = 1; i < LOG; i++){
            up[nxt][i] = up[up[nxt][i - 1]][i - 1];
            pref[nxt][i] = pref[nxt][i - 1] + pref[up[nxt][i - 1]][i - 1];
        }

        dfs(cur, nxt);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;

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

    stack<int>st;

    for(int i = 1; i <= n; i++){    
        while(!st.empty() && d[i] > d[st.top()]){
            p[st.top()] = i;
            st.pop();
        }

        st.push(i);
    }

    for(int i = 1; i <= n; i++){
        adj[i].push_back(p[i]);
        adj[p[i]].push_back(i);
    }

    dfs(-1, 0);

    while(q--){
        ll x, y; cin >> x >> y;
        for(int i = LOG - 1; i >= 0; i--){
            if(pref[x][i] < y){
                y -= pref[x][i];
                x = up[x][i];
            }
        }

        cout << x << '\n';
    }

    return 0;
}

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