Submission #972534

#	Time	Username	Problem	Language	Result	Execution time	Memory
972534		akacool445k	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	944 ms	1048576 KiB

jumps

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

// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;

const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
int n;
int h[mxn] , le[mxn] , ri[mxn];
int inv[mxn];
int spx[19][mxn] , spn[19][mxn];




int s[mxn * 4], suf[mxn * 4];
void build(int id, int L, int R) {
	if(L == R) {
		s[id] = h[L];
		return;
	}
	int x = 2 * id + 1, y = x + 1, M = (L + R) / 2;
	build(x, L, M);
	build(y, M + 1, R);
	s[id] = max(s[x], s[y]);
}
pair<int, int> query(int id, int L, int R, int l, int r, int d) {
	if(L == R) {
		if(s[id] > d) return {-1, 0};
		return {s[id], 1};
	}
	int x = 2 * id + 1, y = x + 1, M = (L + R) / 2;
	if(L == l && R == r) {
		if(s[id] < d) return {s[id], 1};
		pint pr = query(x, L, M, l, r, d);
		if(pr.ss == 0) return pr;
		pint pl = query(y, M + 1, R, l, r, d);
		return {max(pl.ff, pr.ff), 0};
	}
	if(r <= M) return query(x, L, M, l, r, d);
	if(M + 1 <= l) return query(y, M + 1, R, l, r, d);
	pint pr = query(x, M + 1, R, l, r, d);
	if(pr.ss == 0) return pr;
	pint pl = query(y, L, M, l, r, d);
	return {max(pl.ff, pr.ff), pl.ss};

}
void init(int N , vint H) {
	n = N;
	vint v;
	for (int i = 0; i < n; i++) {
		h[i] = H[i];
		inv[h[i]] = i;
	}
	build(0, 0, n - 1);
	for (int i = 0; i < n; i++) {
		while (v.size() > 0 && v.back() < h[i]) {
			ri[v.back()] = h[i];
			v.pop_back();
		}
		if (v.size() > 0) le[h[i]] = v.back();
		v.push_back(h[i]);
	}

	for (int i = 0; i < n; i++) {
		spx[0][h[i]] = max(le[h[i]] , ri[h[i]]);
		spn[0][h[i]] = min(le[h[i]] , ri[h[i]]);
		if (spn[0][h[i]] == 0) spn[0][h[i]] = spx[0][h[i]];
	}

	for (int j = 1; j < 19; j++) {
		for (int i = 0; i < n; i++) {
			spx[j][h[i]] = spx[j-1][spx[j-1][h[i]]];
			spn[j][h[i]] = spn[j-1][spn[j-1][h[i]]];
		}
	}
}

int func(int a , int d) {
	if (h[a] > h[d]) return -1;
	int dis = 0;
	for (int i = 18; i >= 0; i--) {
		if (spx[i][h[a]] > h[d]) continue;
		if (spx[i][h[a]] == h[d]) return (1 << i);
		int t = func(inv[spx[i][h[a]]] , d);
		if(t == -1) {
			return -1;
		}
		return (1 << i) + t;
	}

	for (int i = 18; i >= 0; i--) {
		if (spn[i][h[a]] > h[d]) continue;
		if (spn[i][h[a]] == h[d]) return (1 << i);
		int t = func(inv[spx[i][h[a]]] , d);
		if(t == -1) {
			return -1;
		}
		return (1 << i) + t;
	}

	return -1;
}
int minimum_jumps(int a, int b, int c, int d) {
	int temp = query(0, 0, n - 1, a, b, h[d]).ff;
	if(temp == -1) return -1;
	return func(inv[temp], d);
}

Compilation message (stderr)

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:89:6: warning: unused variable 'dis' [-Wunused-variable]
   89 |  int dis = 0;
      |      ^~~

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