oj.uz

Submission #489557

# Submission time Handle Problem Language Result Execution time Memory
489557 2021-11-23T08:26:09 Z dung11112003 Rainforest Jumps (APIO21_jumps) C++11
4 / 100
 1413 ms 77788 KB 
#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

int n;
vector <int> a, L, R, depth, nxt;
vector <vector <int>> jumpL, jumpR, jumpbest;

void init(int N, vector<int> H)
{
    n = N;
    a = H;
    for (auto &x: a)
    {
        x--;
    }
    L.assign(n, 0);
    R.assign(n, 0);
    stack <int> st;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && a[st.top()] < a[i])
        {
            st.pop();
        }
        L[i] = (st.empty() ? -1 : st.top());
        st.push(i);
    }
    st = stack <int>();
    for (int i = n - 1; i >= 0; i--)
    {
        while (!st.empty() && a[st.top()] < a[i])
        {
            st.pop();
        }
        R[i] = (st.empty() ? n : st.top());
        st.push(i);
    }
    jumpL.assign(n, vector <int> (20));
    for (int i = 0; i < n; i++)
    {
        jumpL[i][0] = L[i];
    }
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i < n; i++)
        {
            jumpL[i][j] = (jumpL[i][j - 1] == -1 ? -1 : jumpL[jumpL[i][j - 1]][j - 1]);
        }
    }
    jumpR.assign(n, vector <int> (20));
    for (int i = 0; i < n; i++)
    {
        jumpR[i][0] = R[i];
    }
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i < n; i++)
        {
            jumpR[i][j] = (jumpR[i][j - 1] == n ? n : jumpR[jumpR[i][j - 1]][j - 1]);
        }
    }
    nxt.assign(n, 0);
    for (int i = 0; i < n; i++)
    {
        if (L[i] == -1)
        {
            nxt[i] = (R[i] == n ? -1 : R[i]);
        }
        else if (R[i] == n)
        {
            nxt[i] = L[i];
        }
        else
        {
            nxt[i] = (a[L[i]] < a[R[i]] ? R[i] : L[i]);
        }
    }
    jumpbest.assign(n, vector <int> (20));
    vector <int> pos(n);
    for (int i = 0; i < n; i++)
    {
        pos[a[i]] = i;
    }
    depth.assign(n, 0);
    for (int i = n - 1; i >= 0; i--)
    {
        int p = pos[i];
        depth[p] = (nxt[p] == -1 ? 0 : depth[nxt[p]] + 1);
        jumpbest[p][0] = nxt[p];
        for (int j = 1; j < 20; j++)
        {
            jumpbest[p][j] = (jumpbest[p][j - 1] == -1 ? -1 : jumpbest[jumpbest[p][j - 1]][j - 1]);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D)
{
    int cur = B;
    for (int i = 19; i >= 0; i--)
    {
        if (jumpR[cur][i] != -1 && jumpR[cur][i] < C)
        {
            cur = jumpR[cur][i];
        }
    }
    if (R[cur] > D)
    {
        return -1;
    }
    int target = R[cur];
    cur = B;
    for (int i = 19; i >= 0; i--)
    {
        if (jumpL[cur][i] >= A && a[jumpL[cur][i]] < a[target])
        {
            cur = jumpL[cur][i];
        }
    }
    int ans = 0;
    for (int i = 19; i >= 0; i--)
    {
        if (jumpbest[cur][i] != -1 && a[jumpbest[cur][i]] <= a[target])
        {
            cur = jumpbest[cur][i];
            ans += 1 << i;
        }
    }
    ans += depth[target] - depth[cur];
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 279 ms 61924 KB Output is correct
4 Correct 1134 ms 77788 KB Output is correct
5 Correct 1111 ms 39232 KB Output is correct
6 Correct 1413 ms 77740 KB Output is correct
7 Correct 1064 ms 53140 KB Output is correct
8 Correct 1384 ms 77716 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 186 ms 62012 KB Output is correct
6 Correct 228 ms 77072 KB Output is correct
7 Correct 101 ms 39564 KB Output is correct
8 Incorrect 223 ms 76928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 322 ms 35364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 322 ms 35364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 279 ms 61924 KB Output is correct
4 Correct 1134 ms 77788 KB Output is correct
5 Correct 1111 ms 39232 KB Output is correct
6 Correct 1413 ms 77740 KB Output is correct
7 Correct 1064 ms 53140 KB Output is correct
8 Correct 1384 ms 77716 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Incorrect 2 ms 200 KB Output isn't correct
14 Halted 0 ms 0 KB -