oj.uz

Submission #772738

# Submission time Handle Problem Language Result Execution time Memory
772738 2023-07-04T10:51:34 Z PAndaS Fountain (eJOI20_fountain) C++14
30 / 100
 662 ms 42696 KB 
#include<iostream>
#include<vector>
#include<stack>
#include<climits>

#define K 20

using namespace std;

vector<vector<long>> up, sum;

long f(long u, long x){
    long res = 0;
    for(long i = 0; x; i++)if(x & (1 << i)){
        res += sum[u][i];
        u = up[u][i];
        x -= (1 << i);
        if(u == -1) break;
    }
    return res;
}

long jump(int u, int x){
    for(long i = 0; x; i++) if(x & (1 << i)){
        u = up[u][i];
        x -= (1 << i);
        if(u == -1) break;
    }
    return u;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long n, q; cin >> n >> q;
    vector<long> c(n), d(n);
    for(long i = 0; i < n; i++) cin >> d[i] >> c[i];
    up.resize(n, vector<long>(K, -1));
    stack<pair<long, long>> st;
    st.push(pair<long, long>(LONG_MAX, -1));
    for(long i = n -1; i + 1; i--){
        while(st.top().first  < d[i]){
            st.pop();
        }
        up[i][0] = st.top().second;
        st.push(pair<long, long>(d[i], i));
    }
    for(long i = 1; i < K; i++) for(long j = 0; j < n; j++)if(up[j][i - 1] + 1) up[j][i] = up[up[j][i - 1]][i - 1];
    sum.resize(n, vector<long>(K, -1));
    for(long i = 0; i < n; i++) sum[i][0] = c[i];
    for(long i = 1; i < K; i++) for(long j = 0; j < n; j++){
        sum[j][i] = sum[j][i - 1];
        if(up[j][i - 1] >= 0) sum[j][i] += sum[up[j][i - 1]][i - 1];
    }
    long res, v;
    long l, m, r;
    for(long i = 0; i < q; i++){
        cin >> res >> v;
        res--;
        l = 0;
        r = n - 1;
        while(l ^ r){
            m = (l + r) / 2;
            if(f(res, m) < v) l = m + 1;
            else r = m;
        }
        cout << jump(res, l - 1) + 1 << '\n';
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 42696 KB Output is correct
2 Correct 662 ms 39696 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -