Submission #1299736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299736		SmuggingSpun	Rainforest Jumps (APIO21_jumps)	C++20	31 / 100	363 ms	45844 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int INF = 2e9;
int n, h[lim], L[lim][18], R[lim][18], best[lim][18];
bool is_sub1 = true;
void init(int __n, vector<int>__h){
	n = __n + 2;
	__h.insert(__h.begin(), INF);
	__h.push_back(INF);
	stack<int>st;
	for(int i = 0; i < n; st.push(i++)){
		if((h[i] = __h[i]) != i + 1){
			is_sub1 = false;
		}
		while(!st.empty() && h[st.top()] < h[i]){
			st.pop();
		}
		L[i][0] = (st.empty() ? i : st.top());
	}
	while(!st.empty()){
		st.pop();
	}
	for(int i = n - 1; i > -1; st.push(i--)){
		while(!st.empty() && h[st.top()] < h[i]){
			st.pop();
		}
		best[i][0] = (h[L[i][0]] > h[R[i][0] = (st.empty() ? i : st.top())] ? L[i][0] : R[i][0]);
	}
	for(int j = 1; j < 18; j++){
		for(int i = 0; i < n; i++){
			L[i][j] = L[L[i][j - 1]][j - 1];
			R[i][j] = R[R[i][j - 1]][j - 1];
			best[i][j] = best[best[i][j - 1]][j - 1];
		}
	}
}
int minimum_jumps(int A, int B, int C, int D){
	A++;
	B++;
	C++;
	D++;
	if(is_sub1){
		return C - B;
	}
  if(n <= 2000){
		queue<int>q;
		vector<int>f(n, -1);
		for(int i = A; i <= B; i++){
			q.push(i);
			f[i] = 0;
		}
		while(!q.empty()){
			int u = q.front();
			q.pop();
			if(C <= u && D >= u){
				return f[u];
			}
			if(f[L[u][0]] == -1){
				f[L[u][0]] = f[u] + 1;
				q.push(L[u][0]);
			}
			if(f[R[u][0]] == -1){
				f[R[u][0]] = f[u] + 1;
				q.push(R[u][0]);
			}
		}
		return -1;
	}
	if(A == B && C == D){
		int ans = 0;
		for(int i = 17; i > -1; i--){
			if(h[best[A][i]] <= h[C]){
				A = best[A][i];
				ans |= 1 << i;
			}
		}
		for(int i = 17; i > -1; i--){
			if(h[R[A][i]] <= h[C]){
				A = R[A][i];
				ans += 1 << i;
			}
		}
		return A == C ? ans : -1;
	}
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19