oj.uz

Submission #642843

# Submission time Handle Problem Language Result Execution time Memory
642843 2022-09-20T15:42:41 Z bonk Fountain (eJOI20_fountain) C++14
100 / 100
 294 ms 40644 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5;
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 3 ms 4340 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 3 ms 4580 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 34760 KB Output is correct
2 Correct 215 ms 35544 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 3 ms 4340 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 3 ms 4580 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 3 ms 4452 KB Output is correct
8 Correct 212 ms 34760 KB Output is correct
9 Correct 215 ms 35544 KB Output is correct
10 Correct 3 ms 4524 KB Output is correct
11 Correct 76 ms 21332 KB Output is correct
12 Correct 294 ms 40644 KB Output is correct
13 Correct 170 ms 35584 KB Output is correct
14 Correct 149 ms 33868 KB Output is correct
15 Correct 118 ms 34436 KB Output is correct