Submission #981280

#	Time	Username	Problem	Language	Result	Execution time	Memory
981280		Jawad_Akbar_JJ	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4008 ms	16844 KiB

jumps

#include "jumps.h"
#include <iostream> 
#include <vector>
#include <queue>

using namespace std;
const int N = 2e5 + 10;
vector<int> nei[N];
int lft[N];
int rgt[N];
int Mn[N];
int seen[N];
bool sub1 = true;

void init(int n,vector<int> h){
    vector<int> v;
    
    for (int i=0;i<n;i++)
        sub1 &= (h[i] == i + 1);

    for (int i=0;i<n;i++)
        lft[i] = rgt[i] = -1;
    
    for (int i=0;i<n;i++){
        while (v.size() > 0 and h[v.back()] < h[i])
            rgt[v.back()] = i,v.pop_back();
        v.push_back(i);
    }
    v.clear();

    for (int i=n-1;i>=0;i--){
        while (v.size() > 0 and h[v.back()] < h[i])
            lft[v.back()] = i,v.pop_back();
        v.push_back(i);
    }

    for (int i=0;i<n;i++){
        if (lft[i] != -1)
            nei[i + 1].push_back(lft[i] + 1);
        if (rgt[i] != -1)
            nei[i + 1].push_back(rgt[i] + 1);
    }
}
int cur = 0;
int minimum_jumps(int A, int B, int C, int D) {
    if (sub1)
        return C - B;
    cur++;
    queue<int> Q;

    for (int i=A+1;i<=B + 1;i++)
        Q.push(i),seen[i] = cur,Mn[i] = 0;

    while (!Q.empty()){
        int u = Q.front();
        if (u >= C+1 and u <= D+1)
            return Mn[u];
        Q.pop();
        for (int i : nei[u])
            if (seen[i] != cur)
                Mn[i] = Mn[u] + 1,Q.push(i),seen[i] = cur;
    }
    return -1;
}

• Subtask 1: 4 / 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