Submission #1187241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187241		Aviansh	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4033 ms	23272 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5;
int h[maxn];
vector<int>g[maxn];
int rev[maxn];
int n;

void init(int N, vector<int> H) {
    n=N;
    for(int i = 0;i<n;i++){
        h[i]=H[i];
        rev[h[i]-1]=i;
    }
    set<int>inds;
    for(int i = n-1;i>=0;i--){
        int ind = rev[i];
        if(inds.size()){
            auto it = inds.lower_bound(i);
            if(it!=inds.end()){
                g[ind].push_back(*it);
            }
            if(it!=inds.begin()){
                it--;
                g[ind].push_back(*it);
            }
        }
        inds.insert(rev[i]);
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    int ans = 1e9;
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
    for(int i = a;i<=b;i++){
        pq.push({0,i});
    }
    int dist[n];
    fill(dist,dist+n,1e9);
    while(!pq.empty()){
        array<int,2>curr = pq.top();
        pq.pop();
        if(dist[curr[1]]<=curr[0])
            continue;
        dist[curr[1]]=curr[0];
        for(int i:g[curr[1]]){
            pq.push({curr[0]+1,i});
        }
    }
    for(int i = c;i<=d;i++){
        ans=min(ans,dist[i]);
    }
    if(ans==1e9)
        return -1;
    return ans;
}

• 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