Submission #958340

#	Time	Username	Problem	Language	Result	Execution time	Memory
958340		Itamar	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1519 ms	60080 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
int h[siz];

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();
			maxi = max(sl->maxi, sr->maxi);
		}
		else maxi = { h[l],l };
	}
	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 > b)return { 0,0 };
		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 bin[siz][20][2];
int l[siz], r[siz];
int n;
int ll[siz], rr[siz];
void init(int N, std::vector<int> H) {
	seg[0] = new node(0, N);
	n = N;
	vi his(N + 1);
	for (int i = 0; i < N; i++)h[i] = H[i];
	seg[0]->ini();
	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();
		}
		l[i] = s.top().y;
		ll[i] = s.top().x;
		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();
		}
		r[i] = s.top().y;
		rr[i] = s.top().x;
		s.push({ h[i],i });
	}
	for (int i = 0; i < N; i++) {
		if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1;
		if (rr[i] < ll[i]) {
			swap(ll[i], rr[i]); swap(l[i], r[i]);
		}
		bin[i][0][1] = r[i];
		if (l[i] == -1)bin[i][0][0] = r[i]; else bin[i][0][0] = l[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, mid; pi ps;
	 m = seg[0]->query(C, D).x;
	 //ps = seg[m - 1]->query(A, B);
	 int ss = A, e = B;
	 while (ss < e) {
		 int midmid = (ss + e) / 2;
		 pi p = seg[0]->query(midmid, B);
		 if (p.x > m) {
			 ss = midmid + 1;
		 }
		 else e = midmid;
	 }
	 ps = seg[0]->query(ss, B);
	 mid = seg[0]->query(B + 1, C - 1).x;
	//m = h[C]; ps = { h[A],A }; if (h[A] > h[C])ps.x = 0; mid = 0; for (int i = B + 1; i < C; i++)mid = max(mid, h[i]);
	int s = ps.y;
	if (ps.x>m)return -1;
	if (C == B + 1)return 1;
	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);
			}
		}
	}
	return ans + 2;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:86:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |   if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -1;
      |   ^~
jumps.cpp:86:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |   if (rr[i] == 1e9)rr[i] = -1; if (ll[i] == 1e9)ll[i] = -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