oj.uz

Submission #561377

# Submission time Handle Problem Language Result Execution time Memory
561377 2022-05-12T17:36:40 Z piOOE Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 831 ms 47040 KB 
#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

const int logn = 19, N = 200001;

int h[N], jump[logn][N], R[N], L[N], spt[logn][N], n, jmp[logn][N];
const int infI = 1e9 + 7;

bool okk = true;

int Min(int i, int j) {
    return h[i] < h[j] ? i : j;
}

int Max(int i, int j) {
    return h[i] > h[j] ? i : j;
}

int get_max(int l, int r) {
    if (r <= l) return -1;
    int sz = __lg(r - l);
    return Max(spt[sz][l], spt[sz][r - (1 << sz)]);
}

void init(int nn, vector<int> H) {
    n = nn;
    for (int i = 0; i < n; ++i) {
        h[i] = H[i];
        okk &= (H[i] == i + 1);
    }
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.back()] < h[i]) {
            R[st.back()] = i;
            st.pop_back();
        }
        if (st.empty()) {
            L[i] = -1;
        } else {
            L[i] = st.back();
        }
        st.push_back(i);
    }
    for (int i: st) {
        R[i] = n;
    }
    st.clear();
    for (int i = 0; i < n; ++i) {
        if (R[i] == n)
            jump[0][i] = L[i];
        else if (L[i] == -1)
            jump[0][i] = R[i];
        else
            jump[0][i] = Max(L[i], R[i]);
        jmp[0][i] = R[i];
        spt[0][i] = i;
    }
    jmp[0][n] = n;
    jump[0][n] = -1;
    for (int j = 1; j < logn; ++j) {
        for (int i = 0; i <= n; ++i) {
            if (jump[j - 1][i] != -1)
                jump[j][i] = jump[j - 1][jump[j - 1][i]];
            else
                jump[j][i] = -1;
            jmp[j][i] = jmp[j - 1][jmp[j - 1][i]];
        }
    }
    for (int j = 1; j < logn; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            spt[j][i] = Max(spt[j - 1][i], spt[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (okk) {
        return C - B;
    }
    ++D, ++B;
    int mxcd = get_max(C, D);
    int lx = A - 1, rx = C;
    while (lx + 1 < rx) {
        int m = (lx + rx) >> 1;
        if (h[get_max(m, C)] < h[mxcd]) rx = m;
        else lx = m;
    }
    if (rx >= B) {
        return -1;
    }
    int i = get_max(rx, B);
    int ans = 0;
    for (int j = logn - 1; j > -1; --j) {
        if (jump[j][i] == -1 || h[jump[j][i]] >= h[C]) continue;
        ans += (1 << j);
        i = jump[j][i];
    }
    assert(L[i] != C);
    assert(i < C);
    int nw = ans;
    if (R[i] >= C && R[i] < D) ans = nw + 1;
    else if (jump[0][i] != -1 && h[jump[0][i]] < h[mxcd]) ans = nw + 2;
    for (int j = logn - 1; j > -1; --j) {
        if (jmp[j][i] < C) {
            nw += (1 << j);
            i = jmp[j][i];
        }
    }
    assert(R[i] >= C && R[i] < D);
    return min(ans, nw + 1);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 116 ms 37444 KB Output is correct
4 Correct 831 ms 47008 KB Output is correct
5 Correct 723 ms 23612 KB Output is correct
6 Correct 743 ms 46992 KB Output is correct
7 Correct 640 ms 32032 KB Output is correct
8 Correct 706 ms 47036 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Incorrect 3 ms 464 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 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Incorrect 3 ms 464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 40 ms 37932 KB Output is correct
6 Correct 59 ms 47028 KB Output is correct
7 Correct 23 ms 24008 KB Output is correct
8 Correct 49 ms 46952 KB Output is correct
9 Correct 7 ms 7216 KB Output is correct
10 Correct 51 ms 47008 KB Output is correct
11 Correct 43 ms 47016 KB Output is correct
12 Incorrect 46 ms 47040 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Incorrect 224 ms 21524 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 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Incorrect 224 ms 21524 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 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 116 ms 37444 KB Output is correct
4 Correct 831 ms 47008 KB Output is correct
5 Correct 723 ms 23612 KB Output is correct
6 Correct 743 ms 46992 KB Output is correct
7 Correct 640 ms 32032 KB Output is correct
8 Correct 706 ms 47036 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 0 ms 464 KB Output is correct
12 Correct 0 ms 464 KB Output is correct
13 Incorrect 3 ms 464 KB Output isn't correct
14 Halted 0 ms 0 KB -