oj.uz

Submission #412834

# Submission time Handle Problem Language Result Execution time Memory
412834 2021-05-27T16:13:01 Z blue Fountain (eJOI20_fountain) C++17
100 / 100
 824 ms 25452 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 5 ms 524 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 23824 KB Output is correct
2 Correct 579 ms 22344 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 5 ms 524 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 530 ms 23824 KB Output is correct
9 Correct 579 ms 22344 KB Output is correct
10 Correct 6 ms 460 KB Output is correct
11 Correct 298 ms 14620 KB Output is correct
12 Correct 824 ms 25452 KB Output is correct
13 Correct 667 ms 25132 KB Output is correct
14 Correct 616 ms 24968 KB Output is correct
15 Correct 591 ms 25052 KB Output is correct