Submission #971142

#	Time	Username	Problem	Language	Result	Execution time	Memory
971142		dubabuba	Rainforest Jumps (APIO21_jumps)	C++14	4 / 100	591 ms	15792 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2e5 + 10;
vector<int> adj[mxn];
int dis[mxn];

void init(int N, vector<int> H) {
	vector<int> L(N, -1), R(N, -1);
	stack<int> st; st.push(0);
	for(int i = 1; i < N; i++) {
		while(st.size() && H[st.top()] <= H[i])
			st.pop();
		if(st.size())
			L[i] = st.top();
		st.push(i);
	}

	stack<int> en; en.push(0);
	for(int i = N - 1; i >= 0; i--) {
		while(en.size() && H[en.top()] <= H[i])
			en.pop();
		if(en.size())
			R[i] = en.top();
		en.push(i);
	}

	for(int i = 0; i < N; i++) {
		if(L[i] > -1) adj[i].push_back(L[i]);
		if(R[i] > -1) adj[i].push_back(R[i]);
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	// memset(dis, -1, sizeof dis);
	// priority_queue<pii> pq;
	// for(int i = A; i <= B; i++) {
	// 	pq.push(MP(0, i));
	// }

	// while(pq.size()) {
	// 	int d = -pq.top().ff;
	// 	int u = pq.top().ss;
	// 	pq.pop();

	// 	if(dis[u] > -1) continue;
	// 	dis[u] = d;

	// 	for(int v : adj[u])
	// 		if(dis[v] == -1)
	// 			pq.push(MP(-(d + 1), v));
	// }

	// int ans = INT_MAX;
	// for(int i = C; i <= D; i++)
	// if(dis[i] > -1)
	// 	ans = min(ans, dis[i]);
	// return (ans == INT_MAX) ? -1 : ans;
	return C - B;
}

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