oj.uz

Submission #802993

# Submission time Handle Problem Language Result Execution time Memory
802993 2023-08-02T17:34:08 Z andreiomd Fountain (eJOI20_fountain) C++14
100 / 100
 194 ms 19792 KB 
#include <iostream>
#include <stack>

using namespace std;
using PII = pair<int, int>;

static constexpr int NMAX = (int)(1e5 + 1), LOGMAX = 17;

int N, Q;
int D[NMAX], C[NMAX];

PII Next[LOGMAX][NMAX];

static inline void Read()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;
    for (int i = 1; i <= N; ++i)
        cin >> D[i] >> C[i], Next[0][i] = {0, 0};

    return;
}

static inline void Get_level_0()
{
    stack<int> S;

    for (int i = 1; i <= N; ++i)
    {
        while (!S.empty() && D[i] > D[S.top()])
            Next[0][S.top()].first = i, Next[0][S.top()].second += C[i], S.pop();

        S.push(i);
    }

    return;
}

static inline void Precompute()
{
    for (int i = 1; (1 << i) <= N; ++i)
        for (int j = 1; j <= N; ++j)
            Next[i][j] = {Next[i - 1][Next[i - 1][j].first].first, Next[i - 1][j].second + Next[i - 1][Next[i - 1][j].first].second};

    return;
}

static inline void Test_Case()
{
    int node = 0, target = 0;
    cin >> node >> target;

    if (C[node] >= target)
    {
        cout << node << '\n';
        return;
    }

    if (!Next[0][node].first)
    {
        cout << 0 << '\n';
        return;
    }

    target -= C[node];

    for (int i = 16; i >= 0; --i)
        if (Next[i][node].first)
            if (target - Next[i][node].second >= 0)
                target -= Next[i][node].second, node = Next[i][node].first;

    if (target == 0)
        cout << node;
    else
        cout << Next[0][node].first;

    cout << '\n';

    return;
}

static inline void Solve()
{
    for (int q = 1; q <= Q; ++q)
        Test_Case();

    return;
}

int main()
{
    Read();

    Get_level_0();

    Precompute();

    Solve();

    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 17432 KB Output is correct
2 Correct 117 ms 16584 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 97 ms 17432 KB Output is correct
9 Correct 117 ms 16584 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 61 ms 9948 KB Output is correct
12 Correct 194 ms 19792 KB Output is correct
13 Correct 117 ms 19220 KB Output is correct
14 Correct 103 ms 18424 KB Output is correct
15 Correct 65 ms 19144 KB Output is correct