Submission #569501

#	Time	Username	Problem	Language	Result	Execution time	Memory
569501		S2speed	Rainforest Jumps (APIO21_jumps)	C++17	27 / 100	1209 ms	72248 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>

using namespace std;
 
#pragma GCC optimize ("Ofast")
 
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
 
const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;
 
ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}
 
inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

struct segtree {

	int sz = 1;
	vector<int> val;

	void init(int n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , 0);
		return;
	}

	void build(vector<int> &a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = a[lx];
			}
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(a , ln , lx , m); build(a , rn , m , rx);
		val[x] = max(val[ln] , val[rn]);
		return;
	}

	void build(vector<int> &a){
		build(a , 0 , 0 , sz);
		return;
	}

	void set(int i , int k , int x , int lx , int rx){
		if(rx - lx == 1){
			val[x] = k;
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			set(i , k , ln , lx , m);
		} else {
			set(i , k , rn , m , rx);
		}
		val[x] = max(val[ln] , val[rn]);
		return;
	}

	void set(int i , int k){
		set(i , k , 0 , 0 , sz);
		return;
	}

	int cal(int l , int r , int x , int lx , int rx){
		if(rx <= l || lx >= r) return 0;
		if(rx <= r && lx >= l) return val[x];
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		int a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return max(a , b);
	}

	int cal(int l , int r){
		return cal(l , r , 0 , 0 , sz);
	}

	void clear(){
		sz = 1;
		val.clear();
		return;
	}

};

int n;
segtree st;
vector<int> a , v;
int lf[maxn] , rt[maxn] , jal[maxn][20] , jar[maxn][20] , jan[maxn][20] , jax[maxn][20];
vector<pii> u;
int p[maxn];

void init(int N, vector<int> H){
	memset(jal , -1 , sizeof(jal));
	memset(jar , -1 , sizeof(jar));
	memset(jan , -1 , sizeof(jan));
	memset(jax , -1 , sizeof(jax));
	a = H;
	n = N;
	for(int i = 0 ; i < n ; i++){
		p[a[i]] = i;
	}
	for(int i = 0 ; i < n ; i++){
		int h = -1;
		while(!v.empty()){
			int j = v.back();
			if(a[j] > a[i]){
				h = j;
				break;
			}
			v.pop_back();
		}
		lf[i] = h;
		v.push_back(i);
	}
	v.clear();
	for(int i = n - 1 ; ~i ; i--){
		int h = -1;
		while(!v.empty()){
			int j = v.back();
			if(a[j] > a[i]){
				h = j;
				break;
			}
			v.pop_back();
		}
		rt[i] = h;
		v.push_back(i);
	}
	for(int i = 0 ; i < n ; i++){
		jal[i][0] = lf[i];
		for(int j = 1 ; j < 20 ; j++){
			if(jal[i][j - 1] == -1) break;
			jal[i][j] = jal[jal[i][j - 1]][j - 1];
		}
	}
	for(int i = n - 1 ; ~i ; i--){
		jar[i][0] = rt[i];
		for(int j = 1 ; j < 20 ; j++){
			if(jar[i][j - 1] == -1) break;
			jar[i][j] = jar[jar[i][j - 1]][j - 1];
		}
	}
	for(int i = 0 ; i < n ; i++){
		u.push_back({a[i] , i});
	}
	sort(all(u) , greater<pii>());
	for(int e = 1 ; e < n ; e++){
		int i = u[e].second;
		if(lf[i] == -1){
			jax[i][0] = rt[i];
		} else if(rt[i] == -1){
			jax[i][0] = lf[i];
		} else {
			if(a[lf[i]] > a[rt[i]]){
				jax[i][0] = lf[i];
				jan[i][0] = rt[i];
			} else {
				jax[i][0] = rt[i];
				jan[i][0] = lf[i];
			}
		}
		for(int j = 1 ; j < 20 ; j++){
			if(jax[i][j - 1] == -1) break;
			jax[i][j] = jax[jax[i][j - 1]][j - 1];
		}
		for(int j = 1 ; j < 20 ; j++){
			if(jan[i][j - 1] == -1) break;
			jan[i][j] = jan[jan[i][j - 1]][j - 1];
		}
	}
	st.init(n);
	st.build(a);
	return;
}

int dis(int x , int y){
	int res = 0;
	for(int j = 19 ; ~j ; j--){
		int h = jax[x][j];
		if(h == -1) continue;
		if(a[h] > a[y]) continue;
		res += (1 << j);
		x = h;
	}
	for(int j = 19 ; ~j ; j--){
		int h = jan[x][j];
		if(h == -1) continue;
		if(a[h] > a[y]) continue;
		res += (1 << j);
		x = h;
	}
	return res;
}

int minimum_jumps(int l1, int r1, int l2, int r2){
	r1++; r2++;
	if(r1 == l1){
		if(rt[r1 - 1] == -1 || rt[r1 - 1] >= r2) return -1;
		return 1;
	}
	int d = st.cal(r1 , l2) , k = st.cal(l2 , r2);
	if(d > k) return -1;
	if(a[r1 - 1] > d){
		if(a[r1 - 1] > k) return -1;
		return 1;
	}
	int v = r1 - 1;
	for(int j = 19 ; ~j ; j--){
		int h = jal[v][j];
		if(h < l1) continue;
		if(a[h] > d) continue;
		v = h;
	}
	int res = dis(v , p[d]) + 1;
	if(lf[v] >= l1) return 1;
	int o = v;
	for(int j = 19 ; ~j ; j--){
		int h = jal[o][j];
		if(h == -1) continue;
		if(a[h] > d) continue;
		o = h;
	}
	o = lf[o];
	if(o == -1) return res;
	if(a[o] > k) return res;
	res = min(res , dis(v , o) + 1);
	return res;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19