Submission #814800

#	Time	Username	Problem	Language	Result	Execution time	Memory
814800		sentheta	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1217 ms	70732 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#ifdef VANWIJ
	#define DBG 1
#else
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

const int N = 2e5+5;
const int LN = 18;

int n;
int a[N];

V<int> adj[N];
int pl[N][LN], pr[N][LN];
int hi[N][LN], lo[N][LN];


void init(int _n, V<int> _a){
	n = _n;
	rep(i,0,n){
		adj[i].clear();
		a[i] = _a[i];
	}
	
	// leftward edges
	V<int> stak;
	rep(i,0,n){
		while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
		int j = stak.empty() ? i : stak.back();
		pl[i][0] = j;
		if(i!=j) adj[i].push_back(j);
		stak.push_back(i);
	}

	// rightward edges
	stak.clear();
	for(int i=n-1; i>=0; i--){
		while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
		int j = stak.empty() ? i : stak.back();
		pr[i][0] = j;
		if(i!=j) adj[i].push_back(j);
		stak.push_back(i);
	}
	
	rep(i,0,n){
		if(adj[i].empty()) adj[i].push_back(i);
		if(adj[i].size()==1) adj[i].push_back(adj[i][0]);
		
		if(!(a[adj[i][0]] <= a[adj[i][1]])){
			swap(adj[i][0], adj[i][1]);
		}
		lo[i][0] = adj[i][0];
		hi[i][0] = adj[i][1];
	}
	
	
	rep(lg,1,LN) rep(i,0,n){
		pl[i][lg] = pl[pl[i][lg-1]][lg-1];
		pr[i][lg] = pr[pr[i][lg-1]][lg-1];
		
		hi[i][lg] = hi[hi[i][lg-1]][lg-1];
		lo[i][lg] = lo[lo[i][lg-1]][lg-1];
	}
	

	
}

int minimum_jumps(int A,int B,int C,int D){
	// touching
	if(B==C-1){
		if(pr[B][0] <= D) return 1;
		return -1;
	}
	
	// maximum in [B+1..C-1]
	int m = B+1;
	for(int b=LN-1; b>=0; b--){
		int x = pr[m][b];
		if(x<C) m = x;
	}
	if(!(pr[m][0] <= D)) return -1;
	
	// maximum in [C..D]
	int t = C;
	for(int b=LN-1; b>=0; b--){
		int x = pr[t][b];
		if(x<=D) t = x;
	}
	
	// maximum in [A..B] that can reach [C..D]
	int s = B;
	for(int b=LN-1; b>=0; b--){
		int x = pl[s][b];
		if(A<=x && a[x]<=a[t]) s = x;
	}
	
	// impossible
	if(!(a[s] < a[t])) return -1;
	if(!(a[m] < a[t])) return -1;
	// directly connected, i.e. jump over m
	for(int x : adj[s]){
		if(C<=x && x<=D) return 1;
	}
	// WLOG a[s] < a[m]

	
	int ans = 0;
	
	
	// hi edges
	for(int b=LN-1; b>=0; b--){
		bool ok = 1;
		int x = hi[s][b];
		
		if(a[x]<=a[m]){
			s = x;
			ans += 1<<b;
		}
	}
	
	// jump over m
	if(C<=pr[s][0] && pr[s][0]<=D) return ans+1;
	if(C<=pr[pl[s][0]][0] && pr[pl[s][0]][0]<=D) return ans+2;
	
	
	// rightward edges
	// leftward is not possible, since it coulve been skippable
	for(int b=LN-1; b>=0; b--){
		bool ok = 1;
		int x = pr[s][b];
		
		if(x < C){
			s = x;
			ans += 1<<b;
		}
	}
	s = pr[s][0];
	ans++;
	assert(C<=s && s<=D);
	
	return ans;
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:136:8: warning: unused variable 'ok' [-Wunused-variable]
  136 |   bool ok = 1;
      |        ^~
jumps.cpp:153:8: warning: unused variable 'ok' [-Wunused-variable]
  153 |   bool ok = 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