oj.uz

Submission #772652

# Submission time Handle Problem Language Result Execution time Memory
772652 2023-07-04T09:58:53 Z PAndaS Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 46132 KB 
#include<bits/stdc++.h>

#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;
}

void fill_c_d(){
    c.resize(n);
    d.resize(n);
    for(long i = 0; i < n; i++) cin >> d[i] >> c[i];
}

void fill_up(){
    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]; else up[j][i] = -1;
}

void fill_sum(){
    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];
    }
}

void fill_all(){
    cin >> n >> q;
    fill_c_d();
    fill_up();
    fill_sum();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fill_all();
    //Отсюда не ок
    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 1 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 744 KB Output is correct
5 Correct 2 ms 716 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 525 ms 42668 KB Output is correct
2 Correct 610 ms 39808 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 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 744 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 525 ms 42668 KB Output is correct
9 Correct 610 ms 39808 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 264 ms 25148 KB Output is correct
12 Correct 778 ms 46132 KB Output is correct
13 Correct 749 ms 45756 KB Output is correct
14 Correct 255 ms 45132 KB Output is correct
15 Execution timed out 1586 ms 36152 KB Time limit exceeded
16 Halted 0 ms 0 KB -