oj.uz

Submission #561328

# Submission time Handle Problem Language Result Execution time Memory
561328 2022-05-12T16:20:59 Z piOOE Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 806 ms 31800 KB 
#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

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

const int logn = 18, N = 200001;

int h[N], jump[logn][N], R[N], L[N], spt[logn][N];

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 n, vector<int> H) {
    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) {
        jump[0][i] = R[i];
        spt[0][i] = i;
    }
    jump[0][n] = n;
    for (int j = 1; j < logn; ++j) {
        for (int i = 0; i <= n; ++i) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
            if (i + (1 << j) <= n) {
                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;
    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;
    }
    ++B;
    int i = get_max(rx, B);
    auto get = [](int i, int lx, int rx) {
        int ans = 0;
        for (int j = logn - 1; j > -1; --j) {
            if (jump[j][i] < lx) {
                ans += (1 << j);
                i = jump[j][i];
            }
        }
        if (jump[0][i] >= rx) {
            return -1;
        }
        return ans + 1;
    };
    int ans = INT_MAX;
    int added = 0;
    while (i != -1) {
        int nw = get(i, C, D);
        if (nw != -1) {
            ans = min(ans, added + nw);
        }
        ++added;
        i = L[i];
    }
    return (ans == INT_MAX ? -1 : ans);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 72 ms 24860 KB Output is correct
4 Correct 759 ms 31312 KB Output is correct
5 Correct 602 ms 15716 KB Output is correct
6 Correct 769 ms 31296 KB Output is correct
7 Correct 612 ms 21252 KB Output is correct
8 Correct 806 ms 31268 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 39 ms 25124 KB Output is correct
6 Correct 43 ms 31272 KB Output is correct
7 Correct 31 ms 15920 KB Output is correct
8 Correct 43 ms 31312 KB Output is correct
9 Correct 7 ms 4816 KB Output is correct
10 Correct 43 ms 31304 KB Output is correct
11 Correct 38 ms 31396 KB Output is correct
12 Correct 39 ms 31268 KB Output is correct
13 Correct 41 ms 31304 KB Output is correct
14 Correct 47 ms 31304 KB Output is correct
15 Incorrect 47 ms 31800 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 261 ms 14232 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 261 ms 14232 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 72 ms 24860 KB Output is correct
4 Correct 759 ms 31312 KB Output is correct
5 Correct 602 ms 15716 KB Output is correct
6 Correct 769 ms 31296 KB Output is correct
7 Correct 612 ms 21252 KB Output is correct
8 Correct 806 ms 31268 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 2 ms 464 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Incorrect 1 ms 464 KB Output isn't correct
17 Halted 0 ms 0 KB -