Submission #1266310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266310		PlayVoltz	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	583 ms	74820 KiB

jumps

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

vector<int> h;
vector<vector<int> > twokr, twok, twokl;

void init(int n, vector<int> H){
	h.resize(n+2, INT_MAX/2);
	for (int i=0; i<n; ++i)h[i+1]=H[i];
	vector<int> l(n+2), r(n+2);
	stack<int> st;
	st.push(0);
	for (int i=1; i<=n+1; ++i){
		while (h[st.top()]<h[i])r[st.top()]=i, st.pop();
		l[i]=st.top();
		st.push(i);
	}
	twok.resize(n+2, vector<int>(20));
	twokl.resize(n+2, vector<int>(20));
	twokr.resize(n+2, vector<int>(20));
	twok[0][0]=0;
	twok[n+1][0]=n+1;
	twokr[n+1][0]=n+1;
	twokl[0][0]=0;
	for (int i=1; i<=n; ++i){
		twokr[i][0]=r[i];
		twokl[i][0]=l[i];
		if (h[l[i]]>h[r[i]])twok[i][0]=l[i];
		else twok[i][0]=r[i];
	}
	for (int j=1; j<20; ++j)for (int i=0; i<=n+1; ++i)twok[i][j]=twok[twok[i][j-1]][j-1], twokr[i][j]=twokr[twokr[i][j-1]][j-1], twokl[i][j]=twokl[twokl[i][j-1]][j-1];
}

int minimum_jumps(int A, int B, int C, int D){
	int a=A+1, b=B+1, c=C+1, d=D+1, node=b, mx=b+1, ans=0;
	if (b+1==c)return (twokr[b][0]<=d?1:-1);
	for (int i=19; i>=0; --i)if (twokr[mx][i]<=c-1)mx=twokr[mx][i];
	if (h[b]>h[mx])return (twokr[b][0]<=d?1:-1);
	for (int i=19; i>=0; --i)if (twokl[node][i]>=a&&h[twokl[node][i]]<h[mx])node=twokl[node][i];
	if (twokl[node][0]>=a&&twokr[twokl[node][0]][0]<=d)return 1;
	if (twokl[node][0]<a){
		for (int i=19; i>=0; --i)if (h[twok[node][i]]<=h[mx])node=twok[node][i], ans+=(1<<i);
		if (node==mx)return (twokr[node][0]<=d?ans+1:-1);
		if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1;
		if (twokl[node][0]&&c<=twokr[twokl[node][0]][0]&&twokr[twokl[node][0]][0]<=d)return ans+2;
	}
	for (int i=19; i>=0; --i)if (twokr[node][i]<c)node=twokr[node][i], ans+=(1<<i);
	if (c<=twokr[node][0]&&twokr[node][0]<=d)return ans+1;
	return -1;
}

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