oj.uz

Submission #1096990

# Submission time Handle Problem Language Result Execution time Memory
1096990 2024-10-05T16:17:05 Z raphaelp Fountain (eJOI20_fountain) C++14
100 / 100
 458 ms 20424 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> D(N + 1), C(N + 1);
    for (int i = 1; i <= N; i++)
    {
        cin >> D[i] >> C[i];
    }
    vector<vector<int>> lca(log2(N) + 1, vector<int>(N + 1)), lca2(log2(N) + 1, vector<int>(N + 1));
    stack<pair<int, int>> S;
    S.push({0, 1000000002});
    for (int i = N; i > 0; i--)
    {
        while (S.top().second <= D[i])
            S.pop();
        lca[0][i] = S.top().first;
        lca2[0][i] = C[i];
        S.push({i, D[i]});
    }
    lca[0][0] = 0;
    lca2[0][0] = 0;
    for (int i = 1; i <= log2(N); i++)
    {
        for (int j = 0; j <= N; j++)
        {
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
            lca2[i][j] = lca2[i - 1][j] + lca2[i - 1][lca[i - 1][j]];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int r, v;
        cin >> r >> v;
        for (int i = log2(N); i >= 0; i--)
        {
            if (lca2[i][r] < v)
            {
                v -= lca2[i][r];
                r = lca[i][r];
            }
        }
        cout << r << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 5 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 18192 KB Output is correct
2 Correct 340 ms 17408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 299 ms 18192 KB Output is correct
9 Correct 340 ms 17408 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 192 ms 10360 KB Output is correct
12 Correct 458 ms 20424 KB Output is correct
13 Correct 417 ms 19656 KB Output is correct
14 Correct 348 ms 19016 KB Output is correct
15 Correct 334 ms 19152 KB Output is correct