oj.uz

Submission #772476

# Submission time Handle Problem Language Result Execution time Memory
772476 2023-07-04T07:08:02 Z BlockOG Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 21940 KB 
#include <iostream>

using namespace std;

/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

*/

int main() {
    int n, q; cin >> n >> q;

    int diameters[n];
    int capacities[n];
    for (int i = 0; i < n; i++) cin >> diameters[i] >> capacities[i];

    int next[n][20];
    int sum[n][20];
    for (int i = 0; i < n; i++) {
        next[i][0] = -1;
        sum[i][0] = capacities[i];
        for (int j = i + 1; j < n; j++) {
            if (diameters[j] > diameters[i]) {
                next[i][0] = j;
                break;
            }
        }
    }

    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            if (next[i][j - 1] == -1) {
                next[i][j] = -1;
                sum[i][j] = sum[i][j - 1];
                continue;
            }
            next[i][j] = next[next[i][j - 1]][j - 1];
            sum[i][j] = sum[i][j - 1] + sum[next[i][j - 1]][j - 1];
        }
    }

    for (int i = 0; i < q; i++) {
        int r, v; cin >> r >> v; r--;

        for (int i = 19; i >= 0; i--) {
            if (sum[r][i] >= v) continue;
            v -= sum[r][i];
            r = next[r][i];
            if (r == -1) break;
        }

        cout << r + 1 << endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 440 KB Output is correct
7 Correct 4 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 19556 KB Output is correct
2 Correct 356 ms 18504 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 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 440 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 297 ms 19556 KB Output is correct
9 Correct 356 ms 18504 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 232 ms 11620 KB Output is correct
12 Correct 486 ms 21940 KB Output is correct
13 Correct 541 ms 21580 KB Output is correct
14 Correct 367 ms 20748 KB Output is correct
15 Execution timed out 1584 ms 18076 KB Time limit exceeded
16 Halted 0 ms 0 KB -