oj.uz

Submission #772749

# Submission time Handle Problem Language Result Execution time Memory
772749 2023-07-04T10:55:16 Z PAndaS Fountain (eJOI20_fountain) C++14
100 / 100
 894 ms 43768 KB 
#include<iostream>
#include<vector>

#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));
    vector<pair<long, long>> st;
    st.push_back(pair<long, long>(1e9, -1));
    for(long i = n -1; i + 1; i--){
        while(st.back().first <= d[i]){
            st.pop_back();
        }
        up[i][0] = st.back().second;
        st.push_back(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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 41252 KB Output is correct
2 Correct 654 ms 38140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 745 ms 41252 KB Output is correct
9 Correct 654 ms 38140 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 259 ms 23504 KB Output is correct
12 Correct 894 ms 43768 KB Output is correct
13 Correct 754 ms 42444 KB Output is correct
14 Correct 265 ms 42148 KB Output is correct
15 Correct 182 ms 42244 KB Output is correct