oj.uz

Submission #772669

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

#define K 20

using namespace std;

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

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);
    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] >= 0) 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 1 ms 596 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 558 ms 39800 KB Output is correct
2 Correct 595 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 596 KB Output is correct
4 Correct 1 ms 596 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 558 ms 39800 KB Output is correct
9 Correct 595 ms 36848 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 276 ms 23404 KB Output is correct
12 Correct 830 ms 42208 KB Output is correct
13 Correct 790 ms 42228 KB Output is correct
14 Correct 275 ms 42188 KB Output is correct
15 Execution timed out 1569 ms 21352 KB Time limit exceeded
16 Halted 0 ms 0 KB -