Submission #1120006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120006		dsyz	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4059 ms	34076 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N;
bool subtask1 = 1;
vector<ll> v[MAXN];
void init(int n, vector<int> H){
	N = n;
	for(ll i = 0;i < N;i++){
		if(H[i] != i + 1){
			subtask1 = 0;
		}
	}
	stack<ll> s;
	for(ll i = 0;i < N;i++){
		while(!s.empty() && H[s.top()] < H[i]){
			s.pop();
		}
		if(!s.empty()){
			v[i].push_back(s.top());
		}
		s.push(i);
	}
	while(!s.empty()){
		s.pop();
	}
	for(ll i = N - 1;i >= 0;i--){
		while(!s.empty() && H[s.top()] < H[i]){
			s.pop();
		}
		if(!s.empty()){
			v[i].push_back(s.top());
		}
		s.push(i);
	}
}

int minimum_jumps(int A, int B, int C, int D){
	if(subtask1){
		return C - B;
	}
	queue<ll> q;
	ll dist[N];
	memset(dist,-1,sizeof(dist));
	for(ll i = A;i <= B;i++){
		q.push(i);
		dist[i] = 0;
	}
	while(!q.empty()){
		ll x = q.front();
		q.pop();
		for(auto u : v[x]){
			if(dist[u] == -1){
				q.push(u);
				dist[u] = dist[x] + 1;
			}
		}
	}
	ll mini = 1e18;
	for(ll i = C;i <= D;i++){
		if(dist[i] == -1) continue;
		mini = min(mini,dist[i]);
	}
	if(mini == 1e18) return -1;
	else return mini;
}

• 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