Submission #553147

#	Time	Username	Problem	Language	Result	Execution time	Memory
553147		nafis_shifat	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1609 ms	81800 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
int h[mxn];
int n;
int dp1[20][mxn], dp2[20][mxn];
int prv[mxn], nxt[mxn];
int pos[mxn] = {};
struct segtree {
	vector<int> tree[4*mxn];
	int mx[4 * mxn];

	void build(int node,int b,int e) {
		if(b==e) {
			tree[node].push_back(h[b]);
			mx[node] = h[b];
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		build(left,b,mid);
		build(right,mid+1,e);

		mx[node] = max(mx[left], mx[right]);
		tree[node].resize(e - b + 1);
		merge(tree[left].begin(), tree[left].end(), tree[right].begin(), tree[right].end(), tree[node].begin());
	}

	int query(int node, int b, int e, int l, int r, int v) {
		if(b > r || e < l) return 0;
		if(b >= l && e <= r) {
			int p = lower_bound(tree[node].begin(), tree[node].end(), v) - tree[node].begin() - 1;
			if(p < 0) return 0;
			return tree[node][p];
		}

		int mid = b + e >> 1;
		int left = node << 1;
		int right = left | 1;

		return max(query(left, b, mid, l, r, v), query(right, mid + 1, e, l, r, v));

	}

	int get_ind(int node, int b, int e, int p, int v) {
		if(b > p) return 0;
		if(mx[node] <= v) return 0;

		if(b == e) return b;


		int mid = b + e >> 1;
		int left = node << 1;
		int right = left | 1;

		int res = get_ind(right, mid + 1, e, p, v);

		if(res) return res;
		return get_ind(left, b, mid, p, v);
	}

	int rmq(int node, int b, int e, int l, int r) {
		if(b > r || e < l) return 0;
		if(b >= l && e <= r) return mx[node];
		int mid = b + e >> 1;
		int left = node << 1;
		int right = left | 1;
		return max(rmq(left, b, mid, l, r), rmq(right, mid + 1, e, l, r));
	}
} st;
pii go1(int p, int v) {
	int cost = 0;
	for(int i = 19; i >= 0; i--) {
		if(h[dp1[i][p]] <= v) {
			p = dp1[i][p];
			cost += 1 << i;
		}
	}

	return {p, cost};
}

pii go2(int p, int v) {
	int cost = 0;
	for(int i = 19; i >= 0; i--) {
		if(h[dp2[i][p]] <= v) {
			p = dp2[i][p];
			cost += 1 << i;
		}
	}

	return {p, cost};
}
void init(int N, vector<int> H) {
	n = N;
	for(int i = 1; i <= n; i++) {
		h[i] = H[i - 1];
		pos[h[i]] = i;
	}


	st.build(1, 1, n);


	h[0] = inf;

	stack<int> st;


	st.push(0);

	for(int i = 1; i <= n; i++) {
		while(h[st.top()] <= h[i]) st.pop();

		prv[i] = st.top();
		st.push(i);
	}

	while(!st.empty()) st.pop();

	h[n + 1] = inf;

	st.push(n + 1);

	for(int i = n; i >= 1; i--) {
		while(h[st.top()] <= h[i]) st.pop();
		nxt[i] = st.top();
		st.push(i);
	}

	for(int i = 1; i <= n; i++) {
		if(h[prv[i]] > h[nxt[i]]) {
			dp1[0][i] = prv[i];
			dp2[0][i] = nxt[i];
		} else {
			dp1[0][i] = nxt[i];
			dp2[0][i] = prv[i];
		}
	}

	for(int i = 1; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			dp1[i][j] = dp1[i - 1][dp1[i - 1][j]];
			dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
		}
	}


}


int fixed_both(int A, int B) {
	auto [x, cost1] = go1(A, h[B]);
	auto [y, cost2] = go2(x, h[B]);
	if(y == B) return cost1 + cost2;
	return inf;
}

int fixed_target(int A, int B, int C) {
	int id = st.get_ind(1, 1, n, B, h[C]);
	int v = st.query(1, 1, n, max(A, id + 1), B, h[C]);
	if(v == 0) return inf;
	int p = pos[v];
	return fixed_both(p, C);
}


int minimum_jumps(int A, int B, int C, int D) {
	A++;
	B++;
	C++;
	D++;

	int mm = st.rmq(1, 1, n, B + 1, C - 1);

	int mp = pos[mm];

	int ans = inf;

	if(mm != 0 && nxt[mp] <= D) ans = fixed_target(A, B, mp) + 1;


	int lp = st.get_ind(1, 1, n, B, mm);

	if(lp >= A && nxt[lp] <= D) ans = 1;
	else if(lp != 0 && nxt[lp] <= D) {
		int cmx = st.rmq(1, 1, n, A, B);
		ans = min(ans, fixed_both(pos[cmx], lp) + 1);
	}


	if(ans >= inf) return -1;
	return ans;


}

Compilation message (stderr)

jumps.cpp: In member function 'void segtree::build(int, int, int)':
jumps.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid=b+e>>1;
      |           ~^~
jumps.cpp: In member function 'int segtree::query(int, int, int, int, int, int)':
jumps.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = b + e >> 1;
      |             ~~^~~
jumps.cpp: In member function 'int segtree::get_ind(int, int, int, int, int)':
jumps.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int mid = b + e >> 1;
      |             ~~^~~
jumps.cpp: In member function 'int segtree::rmq(int, int, int, int, int)':
jumps.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = b + e >> 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