oj.uz

Submission #569508

# Submission time Handle Problem Language Result Execution time Memory
569508 2022-05-27T12:50:01 Z S2speed Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 207 ms 70604 KB 
#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){
	if(a[l1] > a[l2]) return -1;
	return dis(l1 , l2);
	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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62816 KB Output is correct
2 Correct 34 ms 62888 KB Output is correct
3 Incorrect 185 ms 70604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62920 KB Output is correct
2 Correct 26 ms 62928 KB Output is correct
3 Correct 26 ms 62892 KB Output is correct
4 Correct 27 ms 62908 KB Output is correct
5 Incorrect 33 ms 62928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62920 KB Output is correct
2 Correct 26 ms 62928 KB Output is correct
3 Correct 26 ms 62892 KB Output is correct
4 Correct 27 ms 62908 KB Output is correct
5 Incorrect 33 ms 62928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62928 KB Output is correct
2 Correct 33 ms 62920 KB Output is correct
3 Correct 29 ms 62840 KB Output is correct
4 Correct 32 ms 62912 KB Output is correct
5 Incorrect 118 ms 70164 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62848 KB Output is correct
2 Correct 26 ms 62864 KB Output is correct
3 Correct 25 ms 62848 KB Output is correct
4 Incorrect 207 ms 66956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62848 KB Output is correct
2 Correct 26 ms 62864 KB Output is correct
3 Correct 25 ms 62848 KB Output is correct
4 Incorrect 207 ms 66956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62816 KB Output is correct
2 Correct 34 ms 62888 KB Output is correct
3 Incorrect 185 ms 70604 KB Output isn't correct
4 Halted 0 ms 0 KB -