Submission #412834

#	Time	Username	Problem	Language	Result	Execution time	Memory
412834		blue	Fountain (eJOI20_fountain)	C++17	100 / 100	824 ms	25452 KiB

fountain

#include <iostream>
#include <stack>
using namespace std;

/*

*/

int main()
{
    int N, Q;
    cin >> N >> Q;

    int D[N+2], C[N+2];
    for(int i = 1; i <= N; i++) cin >> D[i] >> C[i];



    int nxt[N+2][18];
    long long vol[N+2][18];
    nxt[N+1][0] = N+1;
    vol[N+1][0] = 2e9;

    D[N+1] = 2e9 + 1;
    stack<int> S;
    S.push(N+1);

    for(int i = N; i >= 1; i--)
    {
        while(D[S.top()] <= D[i]) S.pop();

        nxt[i][0] = S.top();
        vol[i][0] = C[i];

        S.push(i);
    }

    // for(int i = 1; i <= N+1; i++) cerr << nxt[i][0] << ' ';
    // cerr << '\n';

    for(int e = 1; e < 18; e++)
    {
        for(int i = 1; i <= N+1; i++)
        {
            nxt[i][e] = nxt[ nxt[i][e-1] ][e-1];
            vol[i][e] = vol[i][e-1] + vol[ nxt[i][e-1] ][e-1];
        }
    }

    // for(int i = 1; i <= N; i++)
    // {
    //     cerr << i << ": ";
    //
    //     for(int e = 0; e < 4; e++)
    //     {
    //         cerr << nxt[i][e] << ' ' << vol[i][e] << " | ";
    //     }
    //     cerr << '\n';
    // }

    for(int q = 1; q <= Q; q++)
    {
        long long R, V;
        cin >> R >> V;

        for(int e = 17; e >= 0; e--)
        {
            // if(e > 5) continue;
            // cerr << R << ' ' << V << ' ' << vol[R][e] << ' ';
            if(V > vol[R][e])
            {
                V -= vol[R][e];
                R = nxt[R][e];
            }
            // cerr << R << '\n';
        }
        // if(V > 0) R = nxt[R][0];

        if(R == N+1) R = 0;
        cout << R << '\n';
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40