Submission #887829

#	Time	Username	Problem	Language	Result	Execution time	Memory
887829		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1092 ms	50776 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 2e5 + 23;
const int LOG = 20;
const int inf = 2e9;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n;
int a[N];
int le[LOG][N], ri[LOG][N], hi[LOG][N];


void init(int nn, vector<int> h) {
	n = nn;
	// 0 -> 1
	for(int i = 1; i<= n ; i++) a[i] = h[i-1];
	stack<int> st;
	for(int i = 1; i<= n ;i ++) {
		while(sz(st) && a[st.top()] < a[i]) st.pop();
		if(sz(st)) le[0][i] = st.top();
		else le[0][i] = i;
		st.push(i);
	} while(sz(st)) st.pop();
	for(int i = n ; i >= 1;i --) {
		while(sz(st) && a[st.top()] < a[i]) st.pop();
		if(sz(st)) ri[0][i] = st.top();
		else ri[0][i] = i;
		if(a[ri[0][i]] > a[le[0][i]]) hi[0][i] = ri[0][i]; else hi[0][i] = le[0][i];
		st.push(i);
	}
	for(int i = 1; i < LOG; i ++) {
		for(int j = 1; j<= n ; j ++) {
			le[i][j] = le[i-1][le[i-1][j]];
			ri[i][j] = ri[i-1][ri[i-1][j]];
			hi[i][j] = hi[i-1][hi[i-1][j]];
		}
	}
}

int gmx(int l,int r,int bound) {
	// bozorg tarin yaroo ke az bound camtare ve choon mikhaim breim rast bayad az rast shoroo konim
	if(a[r] >= bound) return -1;
	for(int i = LOG-1; i >= 0 ;i --) {
		if(le[i][r] >= l && a[le[i][r]] < bound) r = le[i][r];
	}
	return r;
}

int minimum_jumps(int A, int B, int C, int D) {
	// 0 -> 1
	A++,B++,C++,D++;
	
	int finalboss = gmx(C,D,inf);
	// shoroo bayad az finalboss kamtar bashe mantegan
	int start     = gmx(A,B,a[finalboss]);
	// age shoroo peyda nashod
	if(start == -1) return -1;
	// ye harekat bitch
	if(abs(B-C) == 1) return 1;
	// vasat ye koskeshe oon balast
	int vasat = gmx(B+1,C-1,inf);
	// age vasati dige asan ejaze nadad( kiram dahanesh)
	if(a[vasat] > a[finalboss]) return -1;
	// age bache goli bood
	if(a[vasat] < a[start]) return 1;
	// ta jaii ke mitooni ziad sho ta be vasat beresi
	int ans=0;
	for(int i = LOG-1; i>=0 ;i --) {
		if(a[hi[i][start]] <= a[vasat]) start = hi[i][start], ans += (1 << i);
	}
	// residimo residim
	if(vasat == start) return ans +1;
	if(a[hi[0][start]] < a[finalboss]) return ans + 2;
	for(int i = LOG-1; i>= 0 ; i--) {
		if(ri[i][start] < C) start = ri[i][start], ans += (1<<i);
	}
	return ans +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