Submission #1138281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138281		AbdullahIshfaq	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	410 ms	50564 KiB

jumps

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

const int lg = 20, N = 200005;
int lft[N][lg], rigt[N][lg], mx[N][lg];
vector<int> height;
void init(int n, vector<int> hh){
	height = hh;
	height.insert(height.begin(), 1e9);
	height.insert(height.end(), 1e9);
	n += 2;
	stack<int> que;
	for(int i = 0; i < n; i++){
		while (!que.empty() and height[que.top()] <= height[i]){
			que.pop();
		}
		lft[i][0] = que.empty() ? i : que.top();
		que.push(i);
	}
	while (!que.empty()){
		que.pop();
	}
	for(int i = n - 1; i >= 0; --i){
		while (!que.empty() and height[que.top()] <= height[i]){
			que.pop();
		}
		rigt[i][0] = que.empty() ? i : que.top();
		que.push(i);
	}
	for(int i = 0; i < n; i++){
		if(height[lft[i][0]] > height[rigt[i][0]]){
			mx[i][0] = lft[i][0];
		}
		else{
			mx[i][0] = rigt[i][0];
		}
	}
	for(int j = 1; j < lg; j++){
		for(int i = 0; i < n; i++){
			lft[i][j] = lft[lft[i][j - 1]][j - 1];
			rigt[i][j] = rigt[rigt[i][j - 1]][j - 1];
			mx[i][j] = mx[mx[i][j - 1]][j - 1];
		}
	}
}
int minimum_jumps(int a, int b, int c, int d){
	a++;
	b++;
	c++;
	d++;
	if(b == c - 1){
		if(rigt[b][0] <= d){
			return 1;
		}
		return -1;
	}
	int mid = b + 1;
	for(int j = lg - 1; j >= 0; --j){
		if(rigt[mid][j] <= c - 1){
			mid = rigt[mid][j];    
		}
	}
	if(height[b] > height[mid]){
		if(rigt[b][0] <= d){
			return 1;
		}
		return -1;
	}
	int s = b;
	for(int j = lg - 1; j >= 0; --j){
		if(a <= lft[s][j] and height[lft[s][j]] < height[mid]){
			s = lft[s][j];
		}
	}
	int jmp = 0;
	if(a <= lft[s][0]){
		if(rigt[lft[s][0]][0] <= d){
			return 1;
		}
	}
	else{
		for(int j = lg - 1; j >= 0; --j){
			if(height[mx[s][j]] <= height[mid]){
				jmp |= (1 << j);
				s = mx[s][j];
			}
		}
		if(s == mid){
			if(rigt[s][0] <= d){
				return jmp + 1;
			}
			return -1;
		}
		if(0 < lft[s][0] and rigt[lft[s][0]][0] <= d){
			return jmp + 2;
		}
	}
	for(int j = lg - 1; j >= 0; --j){
		if(rigt[s][j] < c){
			jmp += (1 << j);
			s = rigt[s][j];
		}
	}
	if(c <= rigt[s][0] and rigt[s][0] <= d){
		return jmp + 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