Submission #947469

#	Time	Username	Problem	Language	Result	Execution time	Memory
947469		starchan	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	778 ms	47448 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];

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])
		{
			//printf("Jumped from index x = %d to index v = %d using %d jumps of up.\n\n", x, v, 1<<i);
			ans+=(1<<i);
			x = v;
		}
	}
	for(int i = LOGM-1; i >= 0; i--)
	{
		int v = r[i][x];
		if(arr[v] <= arr[y])
		{
			//printf("Jumped from index x = %d to index v = %d using %d jumps of right.\n\n", x, v, 1<<i);
			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++;
	return min_jumps(a, c);
}

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(4, 4, 6, 6);
	cout << d << endl;
}*/

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