Submission #490800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490800	2021-11-29T10:13:04 Z	SeDunion	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KB

jumps

#include "jumps.h"

#include <vector>
#include <iostream>
#include <math.h>
#include <stack>

using namespace std;

const int LOG = 20;

int pl[int(3e5)], pr[int(3e5)];

int high[int(3e5)][LOG], low[int(3e5)][LOG];

int H[int(3e5)];

void init(int N, vector<int> a) {
	for (int &i : a) i--;
	for (int i = 0 ; i < N ; ++ i) H[i] = a[i];
	H[N] = N;
	stack<int>st;
	for (int i = 0 ; i < N ; ++ i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pl[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	while (st.size()) st.pop();
	for (int i = N - 1 ; i >= 0 ; -- i) {
		while (st.size() && H[st.top()] < H[i]) st.pop();
		pr[H[i]] = st.size() ? H[st.top()] : N;
		st.push(i);
	}
	pl[N] = pr[N] = N;
	for (int i = 0 ; i <= N ; ++ i) {
		high[i][0] = max(pl[i], pr[i]);
		low[i][0] = min(pl[i], pr[i]);
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i <= N ; ++ i) {
			{
				int where = high[i][j - 1];
				high[i][j] = max(high[where][j - 1], high[where][j - 1]);
			}
			{
				int where = low[i][j - 1];
				low[i][j] = min(low[where][j - 1], low[where][j - 1]);
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	assert(A == B && C == D);
	int s = H[A], t = H[C];
	int ans = 0;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (high[s][i] <= t) {
			ans += 1 << i;
			s = high[s][i];
		}
	}
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (low[s][i] <= t) {
			ans += 1 << i;
			s = low[s][i];
		}
	}
	if (s != t) return -1;
	return ans;
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:54:2: error: 'assert' was not declared in this scope
   54 |  assert(A == B && C == D);
      |  ^~~~~~
jumps.cpp:7:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
    6 | #include <stack>
  +++ |+#include <cassert>
    7 |