oj.uz

Submission #788280

# Submission time Handle Problem Language Result Execution time Memory
788280 2023-07-20T04:32:00 Z Em1L Fountain (eJOI20_fountain) C++17
100 / 100
 288 ms 36140 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long

const int K = 18;
const int INF = 1e+15;

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    
    int n, q, pos, v; cin >> n >> q;

    vector < int > d(n + 1), c(n + 1);

    d[0] = 0, c[0] = 1e+9 + 1;
    
    for (int i = 1; i <= n; i++) cin >> d[i] >> c[i];
    
    int p[n + 1][K], pref[n + 1][K];

    for (int i = 0; i <= n; i++)
    {
        for (int k = 0; k < K; k++)
            p[i][k] = 0, pref[i][k] = INF;

        pref[i][0] = 0;
    }

    stack < int > st;
    for (int i = n; i >= 1; i--)
    {
        while (!st.empty() and d[st.top()] <= d[i]) st.pop();
        
        if (!st.empty())
            p[i][0] = st.top(), pref[i][0] = c[i];
        else
            p[i][0] = 0, pref[i][0] = INF;
        
        st.push(i);
    }

    for (int k = 1; k < K; k++)
        for (int i = n; i >= 1; i--)
        {
            p[i][k] = p[p[i][k - 1]][k - 1];

            pref[i][k] = min(INF, pref[i][k - 1] + pref[p[i][k - 1]][k - 1]);

            if (pref[i][k] == pref[i][k - 1]) pref[i][k] = INF;
        }

    for (int i = 0; i < q; i++)
    {
        cin >> pos >> v;
        
        int id = pos;

        for (int k = K - 1; k >= 0 and v > 0; k--)
            if (v > pref[id][k])
                v -= pref[id][k], id = p[id][k];
    
        if (v <= c[id])
            cout << id << '\n';
        else
            cout << p[id][0] << '\n';
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 33024 KB Output is correct
2 Correct 213 ms 30948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 204 ms 33024 KB Output is correct
9 Correct 213 ms 30948 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 63 ms 19148 KB Output is correct
12 Correct 288 ms 36140 KB Output is correct
13 Correct 172 ms 35008 KB Output is correct
14 Correct 136 ms 34148 KB Output is correct
15 Correct 125 ms 34392 KB Output is correct