Submission #542309

#	Time	Username	Problem	Language	Result	Execution time	Memory
542309		penguin133	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	4035 ms	2808 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int X[200005], Y[200005];
void init(int N, vector<int> H){
	n = N;
	stack<int>s;
	for(int i=0;i<n;i++){
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		X[i] = (s.empty() ? -1 : s.top());
		s.push(i);
	}
	while(!s.empty())s.pop();
	for(int i=n-1;i>=0;i--){
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		X[i] = (s.empty() ? -1 : s.top());
		s.push(i);
	}
}

int minimum_jumps(int a, int b, int c, int d){
	queue<int>q;
	int dist[n+1];
	for(int i=0;i<n;i++)dist[i] = 1e9;
	for(int i=a;i<=b;i++)dist[i] = 0, q.push(i);
	while(!q.empty()){
		int x = q.front();q.pop();
		if(X[x] != -1 && dist[X[x]] > dist[x] + 1)dist[X[x]] = dist[x] + 1, q.push(X[x]);
		if(Y[x] != -1 && dist[Y[x]] > dist[x] + 1)dist[Y[x]] = dist[x] + 1, q.push(Y[x]);
	}
	int mini = 1e9;
	for(int i=c;i<=d;i++)mini = min(mini, dist[i]);
	return mini;
}

• 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