oj.uz

Submission #772695

# Submission time Handle Problem Language Result Execution time Memory
772695 2023-07-04T10:32:47 Z cnastea Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 34876 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int u[100000][20];
int s[100000][20];
vector<int> c(100000);

int j(int v, int x){
    bool b[20];
    for(int i = 0; i < 20; i++){
        if((x >> i) & 1) b[i] = 1;
        else b[i] = 0;
    }
    int r = v;
    for(int i = 0; i < 20; i++){
        if(b[i]){
            r = u[r][i];
        }
    }
    return r;
}

int f(int v, int x){
    bool b[20];
    for(int i = 0; i < 20; i++){
        if((x >> i) & 1) b[i] = 1;
        else b[i] = 0;
    }
    int p = 0;
    int r = v;
    for(int i = 0; i < 20; i++){
        if (r == -1) break;
        if(b[i]){
            p += s[r][i];
            r = u[r][i];
        }
    }
    return p;
}

int32_t main()
{
    int n, q;
    cin >> n >> q;
    vector<int> d(n);
    for(int i = 0; i < n; i++){
        cin >> d[i] >> c[i];
    }
    for(int i = 0; i < n; i++){
        for(int k = 0; k < 20; k++) u[i][k] = -1;
    }
    for(int i = 0; i < n; i++){
        for(int k = i+1; k < n; k++){
            if(d[k] > d[i]){
                u[i][0] = k;
                break;
            }
        }
    }
    for(int k = 1; k < 20; k++){
        for(int i = 0; i < n; i++){
            if(u[i][k-1] != -1) u[i][k] = u[u[i][k-1]][k-1];
            else u[i][k] = -1;
        }
    }
    for(int i = 0; i < n; i++){
        s[i][0] = c[i];
    }
    for(int k = 1; k < 20; k++){
        for(int i = 0; i < n; i++){
            if(u[i][k-1] != -1) s[i][k] = s[i][k-1] + s[u[i][k-1]][k-1];
            else s[i][k]=s[i][k-1];
        }
    }
    for(int i = 0; i < q; i++){
        int r, v;
        cin >> r >> v;
        if(v > f(r-1, n-1)) cout << 0 << "\n";
        else{
            int a = 0, b = n;
            int m;
            while(b > a){
                m = (a+b+1)/2;
                if(f(r-1, m) < v) a = m;
                else b = m-1;
            }
            cout << j(r-1, b)+1 << "\n";
        }
    }
    
    return 0;
}

/*
2 1
1 1
1 1
2 1
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 3 ms 1240 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1452 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 32300 KB Output is correct
2 Correct 831 ms 30528 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 3 ms 1240 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1452 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct
8 Correct 737 ms 32300 KB Output is correct
9 Correct 831 ms 30528 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 439 ms 19896 KB Output is correct
12 Correct 1181 ms 34772 KB Output is correct
13 Correct 1059 ms 34876 KB Output is correct
14 Correct 576 ms 34824 KB Output is correct
15 Execution timed out 1558 ms 17960 KB Time limit exceeded
16 Halted 0 ms 0 KB -