oj.uz

Submission #772680

# Submission time Handle Problem Language Result Execution time Memory
772680 2023-07-04T10:20:18 Z PAndaS Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 43224 KB 
#include<iostream>
#include<vector>

#define K 20

using namespace std;

vector<vector<long>> up, sum;
vector<long> c, d;

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;
    c.resize(n);
    d.resize(n);
    for(long i = 0; i < n; i++) cin >> d[i] >> c[i];
    up.resize(n, vector<long>(K, -1));
    for(long i = 0; i < n; i++) for(long j = i + 1; j < n; j++){
        if(d[j] > d[i]){
            up[i][0] = j;
            break;
        }
    }
    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 580 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 39696 KB Output is correct
2 Correct 606 ms 36848 KB Output is correct

Subtask #3
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 580 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 628 ms 39696 KB Output is correct
9 Correct 606 ms 36848 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 288 ms 24384 KB Output is correct
12 Correct 840 ms 43224 KB Output is correct
13 Correct 805 ms 43192 KB Output is correct
14 Correct 310 ms 43172 KB Output is correct
15 Execution timed out 1578 ms 22420 KB Time limit exceeded
16 Halted 0 ms 0 KB -