oj.uz

Submission #465486

# Submission time Handle Problem Language Result Execution time Memory
465486 2021-08-16T08:30:02 Z dfistric Fountain (eJOI20_fountain) C++14
100 / 100
 784 ms 22976 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e5 + 5;

int n, q;
pii info[MAXN], child_pow2[MAXN][20];

vector <pii> available;

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> info[i].f >> info[i].s;

    for(int i = n; i >= 1; i--){
        while(!available.empty() && available.back().f <= info[i].f) available.pop_back();

        if(available.empty()) child_pow2[i][0] = {0, info[i].s};
        else child_pow2[i][0] = {available.back().s, info[i].s};

        available.push_back({info[i].f, i});
    }

    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            pii child = child_pow2[child_pow2[i][j - 1].f][j - 1];
            child_pow2[i][j] = {child.f, child_pow2[i][j - 1].s + child.s};
        }
    }

    while(q--){
        int ind, amount;
        cin >> ind >> amount;

        for(int i = 19; i >= 0; i--){
            if(amount > child_pow2[ind][i].s){
                amount -= child_pow2[ind][i].s;
                ind = child_pow2[ind][i].f;
            }
        }

        cout << ind << '\n';
    }

return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 20396 KB Output is correct
2 Correct 601 ms 19548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 520 ms 20396 KB Output is correct
9 Correct 601 ms 19548 KB Output is correct
10 Correct 6 ms 500 KB Output is correct
11 Correct 297 ms 11820 KB Output is correct
12 Correct 784 ms 22976 KB Output is correct
13 Correct 683 ms 21784 KB Output is correct
14 Correct 609 ms 20836 KB Output is correct
15 Correct 584 ms 21044 KB Output is correct