Submission #947481

#	Time	Username	Problem	Language	Result	Execution time	Memory
947481		starchan	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1081 ms	47568 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e9
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int LOGM = 19;
const int MX = 2e5+5;
vector<int> arr;
int l[LOGM][MX];
int r[LOGM][MX];
int up[LOGM][MX];
//min_jumps is now known to be correct. :)
int min_jumps(int x, int y)
{
	int ans = 0;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int v = up[i][x];
		if(arr[v] <= arr[y])
		{
			ans+=(1<<i);
			x = v;
		}
	}
	for(int i = LOGM-1; i >= 0; i--)
	{
		int v = r[i][x];
		if(arr[v] <= arr[y])
		{
			ans+=(1<<i);
			x = v;
		}
	}
	if(x == y)
		return ans;
	return -1;
}

int minimum_jumps(int a, int b, int c, int d)
{
	a++; b++; c++; d++;
	int c1 = b;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int lift = r[i][c1];
		if(lift < c)
			c1 = lift;
	}
	c1 = r[0][c1];
	if(c1 > d)
		return -1;
	int c2 = c1;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int lift = r[i][c2];
		if(lift <= d)
			c2 = lift;
	} 
	int st = b;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int lift = l[i][st];
		if((lift >= a) && (arr[lift] <= arr[c2]))
			st = lift;
	}
	for(int i = LOGM-1; i >= 0; i--)
	{
		int lift = r[i][c1];
		if(arr[lift] <= arr[st])
			c1 = lift;
	}
	if(arr[c1] <= arr[st])
		c1 = r[0][c1];
	int one = min_jumps(st, c1);
	int ans = 0;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int lift = up[i][st];
		if(arr[lift] <= arr[c1])
		{
			ans+=(1<<i);
			st = lift;
		}
	}
	st = l[0][st];
	if(arr[r[0][st]] <= arr[c2])
		return min(one, ans+2);
	else
		return one;
}

void init(int n, vector<int> h)
{
	arr.resize(n+2);
	for(int i = 1; i <= n; i++)
		arr[i] = h[i-1];
	arr[0] = INF;
	arr[n+1] = INF;
	l[0][0] = 0;
	r[0][0] = n+1;
	l[0][n+1] = 0;
	r[0][n+1] = n+1;
	for(int i = 1; i <= n; i++)
	{
		l[0][i] = i-1;
		r[0][i] = i+1;
	}
	for(int i = 1; i <= n; i++)
	{
		while(arr[l[0][i]] <= arr[i])
			l[0][i] = l[0][l[0][i]];
	}
	for(int i = n; i >= 1; i--)
	{
		while(arr[r[0][i]] <= arr[i])
			r[0][i] = r[0][r[0][i]];
	}
	for(int i = 0; i <= n+1; i++)
	{
		if(arr[l[0][i]] >= arr[r[0][i]])
			up[0][i] = l[0][i];
		else
			up[0][i] = r[0][i];
	}
	for(int i = 1; i < LOGM; i++)
	{
		for(int u = 0; u <= n+1; u++)
		{
			l[i][u] = l[i-1][l[i-1][u]];
			r[i][u] = r[i-1][r[i-1][u]];
			up[i][u] = up[i-1][up[i-1][u]];
		}
	}
}
/*signed main()
{
	init(7, {3, 2, 1, 6, 4, 5, 7});
	int d = minimum_jumps(0, 1, 2, 2);
	cout << d << endl;
}*/

• 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