Submission #859590

#	Time	Username	Problem	Language	Result	Execution time	Memory
859590		boris_mihov	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4017 ms	5200 KiB

jumps

#include "jumps.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 20;
const llong INF = 1e18;
const int INTINF = 2e9;

int n;
int h[MAXN];
int firstR[MAXN];
int firstL[MAXN];
std::stack <int> st;

void init(int N, std::vector <int> H) 
{
    n = N;
    for (int i = 0 ; i < n ; ++i)
    {
        h[i + 1] = H[i];
    }

    h[0] = h[n + 1] = INTINF;
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (st.size() && h[i] > h[st.top()])
        {
            st.pop();
        }

        firstL[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();
    st.push(n + 1);

    for (int i = n ; i >= 1 ; --i)
    {
        while (st.size() && h[i] > h[st.top()])
        {
            st.pop();
        }

        firstR[i] = st.top();
        st.push(i);
    }
}

int minimum_jumps(int a, int b, int c, int d) 
{
    a++; b++; c++; d++;

    int pos = -1;
    int maxC = 0;
    for (int i = c ; i <= d ; ++i)
    {
        maxC = std::max(maxC, h[i]);
    }

    for (int i = a ; i <= b ; ++i)
    {
        if (h[i] <= maxC && firstR[i] > b)
        {
            pos = i;
            break;
        }
    }

    if (pos == -1)
    {
        return -1;
    }

    int res = 0;
    while (pos < c)
    {
        if (h[firstL[pos]] > maxC && h[firstR[pos]] > maxC)
        {
            return -1;
        }

        if (h[firstL[pos]] <= maxC && (firstR[pos] > d || h[firstL[pos]] > h[firstR[pos]]))
        {
            res++;
            pos = firstL[pos];
        } else
        {
            res++;
            pos = firstR[pos];
        }
    }

    return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19