Submission #859599

#	Time	Username	Problem	Language	Result	Execution time	Memory
859599		boris_mihov	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4086 ms	16728 KiB

jumps

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

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::vector <int> g[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 (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 (h[i] > h[st.top()])
        {
            st.pop();
        }

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

    for (int i = 1 ; i <= n ; ++i)
    {
        g[i].push_back(firstL[i]);
        g[i].push_back(firstR[i]);
    }
}

int dists[MAXN];
std::queue <int> q;
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;
    }

    std::fill(dists + 1, dists + 1 + n, -1);
    dists[pos] = 0;
    q.push(pos);

    while (!q.empty())
    {
        int top = q.front();
        q.pop();

        for (const int &u : g[top])
        {
            if (dists[u] == -1)
            {
                dists[u] = dists[top] + 1;
                q.push(u);
            }
        }
    }   

    int min = c;
    for (int i = c + 1 ; i <= d ; ++i)
    {
        if (dists[i] != -1 && (dists[min] == -1 || dists[min] > dists[i]))
        {
            min = i;
        }
    }

    return dists[min];
}

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