Submission #958316

#	Time	Username	Problem	Language	Result	Execution time	Memory
958316		Itamar	Rainforest Jumps (APIO21_jumps)	C++14	4 / 100	1272 ms	234124 KiB

jumps

#include "jumps.h"
using namespace std;
#include <vector>
#include <stack>
#include <algorithm>
#define vi vector<int>
const int siz = 2e5 + 2;
#define pi pair<int,int>
#define x first
#define y second
struct node {
	int l, r, mid;
	pi maxi ={0,0};
	node* sl=NULL, * sr=NULL;
	node(int li, int ri) {
		l = li, r = ri, mid = (l + r) / 2;
	}
	void ini() {
		if (l < r) {
			sl = new node(l, mid);
			sr = new node(mid + 1, r);
			sl->ini(); sr->ini();
		}
	}
	void open(int i, pi val, node* no) {
		maxi = max(no->maxi, val);
		if (l < r) {
			if (i <= mid) {
				sr = no->sr;
				sl = new node(l, mid); sl->open(i, val, no->sl);
			}
			else {
				sl = no->sl;
				sr = new node(mid + 1, r); sr->open(i, val, no->sr);
			}
		}
	}
	pi query(int a, int b) {
		if (a > r || b < l)return { 0,a };
		if (a <= l && b >= r)return maxi;
		return max(sl->query(a,b), sr->query(a,b));
	}
};

node* seg[siz];
int h[siz];
int bin[siz][20][2];
int l[siz], r[siz];
int n;
void init(int N, std::vector<int> H) {
	seg[0] = new node(0, N);
	n = N;
	seg[0]->ini();
	vi his(N + 1);
	for (int i = 0; i < N; i++)h[i] = H[i];
	for (int i = 0; i < N; i++)his[H[i]] = i;
	for (int i = 1; i <= N; i++) {
		seg[i] = new node(0, N);
		seg[i]->open(his[i], { i,his[i] }, seg[i - 1]);
	}
	stack<pi> s; s.push({ 1e9,-1 });
	for (int i = 0; i < N; i++) {bin[i][0][0] = -1, bin[i][0][1] = -1;}
	for (int i = 0; i < N; i++) {
		while (s.top().x < h[i]) {
			s.pop();
		}
		int a = s.top().y;
		l[i] = a;
		s.push({ h[i],i });
	}
	while (s.size() > 1)s.pop();
	for (int i = N - 1; i >= 0; i--) {
		while (s.top().x < h[i]) {
			s.pop();
		}
		int a = s.top().y;
		r[i] = a;
		s.push({ h[i],i });
	}
	for (int i = 0; i < N; i++) {
		bin[i][0][1] = max(l[i], r[i]);
		if (min(l[i], r[i]) == -1)bin[i][0][0] = bin[i][0][1]; else bin[i][0][0] = min(l[i], r[i]);

	}
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < N; i++) {
			for (int k = 0; k < 2; k++) {
				if (bin[i][j - 1][k] >= 0)bin[i][j][k] = bin[bin[i][j - 1][k]][j - 1][k];
				else bin[i][j][k] = -1;
			}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	int ans = 0;
	int m = seg[n]->query(C, D).x;
	pi ps = seg[m - 1]->query(A, B);
	int s = ps.y;
	if (ps.x == 0)return -1;
	if (C == B + 1)return 1;
	int mid = seg[n]->query(B + 1, C - 1).x;
	if (mid > m)return -1;
	if (mid < ps.x)return 1;
	for (int d = 19; d >= 0; d--) {
		int st = bin[s][d][1];
		if (st != -1) {
			if (h[st] < mid) {
				s = st;
				ans += (1 << d);
			}
		}
	}
	if (h[bin[s][0][1]] < m)return ans + 2;
	for (int d = 19; d >= 0; d--) {
		int st = bin[s][d][0];
		if (st != -1) {
			if (h[st] < mid) {
				s = st;
				ans += (1 << d);
			}
		}
	}
	if (h[bin[s][0][0]] < m)return ans + 2;
	return -1;
}

• Subtask 1: 4 / 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