Submission #788280

#	Time	Username	Problem	Language	Result	Execution time	Memory
788280		Em1L	Fountain (eJOI20_fountain)	C++17	100 / 100	288 ms	36140 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40