oj.uz

Submission #642842

# Submission time Handle Problem Language Result Execution time Memory
642842 2022-09-20T15:42:27 Z bonk Fountain (eJOI20_fountain) C++14
30 / 100
 4 ms 980 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 656 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 656 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Runtime error 4 ms 980 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -