oj.uz

Submission #569517

# Submission time Handle Problem Language Result Execution time Memory
569517 2022-05-27T12:54:35 Z S2speed Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1160 ms 72256 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 (x == y ? res : -2);
}

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;
	int h = dis(v , o);
	if(h != -2){
		res = min(res , h + 1);
		if(res == -1) res = h + 1;
	}
	return res;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62876 KB Output is correct
2 Correct 24 ms 62880 KB Output is correct
3 Correct 181 ms 70672 KB Output is correct
4 Correct 994 ms 72084 KB Output is correct
5 Correct 958 ms 67724 KB Output is correct
6 Correct 1160 ms 72084 KB Output is correct
7 Correct 919 ms 69868 KB Output is correct
8 Correct 1156 ms 72116 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62924 KB Output is correct
2 Correct 26 ms 62932 KB Output is correct
3 Correct 30 ms 62884 KB Output is correct
4 Correct 26 ms 62888 KB Output is correct
5 Incorrect 25 ms 62888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62924 KB Output is correct
2 Correct 26 ms 62932 KB Output is correct
3 Correct 30 ms 62884 KB Output is correct
4 Correct 26 ms 62888 KB Output is correct
5 Incorrect 25 ms 62888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62936 KB Output is correct
2 Correct 23 ms 62868 KB Output is correct
3 Correct 24 ms 62928 KB Output is correct
4 Correct 29 ms 62868 KB Output is correct
5 Correct 103 ms 70172 KB Output is correct
6 Correct 128 ms 71372 KB Output is correct
7 Correct 65 ms 67300 KB Output is correct
8 Correct 120 ms 71312 KB Output is correct
9 Correct 42 ms 64164 KB Output is correct
10 Correct 122 ms 71340 KB Output is correct
11 Correct 88 ms 72104 KB Output is correct
12 Incorrect 86 ms 71844 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62832 KB Output is correct
2 Correct 24 ms 62848 KB Output is correct
3 Correct 24 ms 62924 KB Output is correct
4 Correct 302 ms 66940 KB Output is correct
5 Correct 731 ms 71368 KB Output is correct
6 Correct 581 ms 64624 KB Output is correct
7 Correct 778 ms 71328 KB Output is correct
8 Correct 596 ms 66236 KB Output is correct
9 Correct 985 ms 71352 KB Output is correct
10 Correct 1002 ms 72156 KB Output is correct
11 Correct 1088 ms 72256 KB Output is correct
12 Correct 1006 ms 71992 KB Output is correct
13 Correct 906 ms 71368 KB Output is correct
14 Correct 1160 ms 71768 KB Output is correct
15 Correct 769 ms 72124 KB Output is correct
16 Correct 693 ms 72132 KB Output is correct
17 Correct 26 ms 62864 KB Output is correct
18 Correct 26 ms 62928 KB Output is correct
19 Correct 27 ms 62920 KB Output is correct
20 Correct 26 ms 62944 KB Output is correct
21 Correct 26 ms 62932 KB Output is correct
22 Correct 28 ms 62900 KB Output is correct
23 Correct 26 ms 62928 KB Output is correct
24 Correct 29 ms 62844 KB Output is correct
25 Correct 25 ms 62928 KB Output is correct
26 Correct 27 ms 62932 KB Output is correct
27 Correct 52 ms 63048 KB Output is correct
28 Correct 48 ms 63024 KB Output is correct
29 Correct 47 ms 62976 KB Output is correct
30 Correct 42 ms 63024 KB Output is correct
31 Correct 55 ms 63024 KB Output is correct
32 Correct 25 ms 62820 KB Output is correct
33 Correct 88 ms 67724 KB Output is correct
34 Correct 116 ms 71340 KB Output is correct
35 Correct 83 ms 72012 KB Output is correct
36 Correct 119 ms 71344 KB Output is correct
37 Correct 160 ms 71764 KB Output is correct
38 Correct 114 ms 72076 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62832 KB Output is correct
2 Correct 24 ms 62848 KB Output is correct
3 Correct 24 ms 62924 KB Output is correct
4 Correct 302 ms 66940 KB Output is correct
5 Correct 731 ms 71368 KB Output is correct
6 Correct 581 ms 64624 KB Output is correct
7 Correct 778 ms 71328 KB Output is correct
8 Correct 596 ms 66236 KB Output is correct
9 Correct 985 ms 71352 KB Output is correct
10 Correct 1002 ms 72156 KB Output is correct
11 Correct 1088 ms 72256 KB Output is correct
12 Correct 1006 ms 71992 KB Output is correct
13 Correct 906 ms 71368 KB Output is correct
14 Correct 1160 ms 71768 KB Output is correct
15 Correct 769 ms 72124 KB Output is correct
16 Correct 693 ms 72132 KB Output is correct
17 Correct 26 ms 62864 KB Output is correct
18 Correct 26 ms 62928 KB Output is correct
19 Correct 27 ms 62920 KB Output is correct
20 Correct 26 ms 62944 KB Output is correct
21 Correct 26 ms 62932 KB Output is correct
22 Correct 28 ms 62900 KB Output is correct
23 Correct 26 ms 62928 KB Output is correct
24 Correct 29 ms 62844 KB Output is correct
25 Correct 25 ms 62928 KB Output is correct
26 Correct 27 ms 62932 KB Output is correct
27 Correct 52 ms 63048 KB Output is correct
28 Correct 48 ms 63024 KB Output is correct
29 Correct 47 ms 62976 KB Output is correct
30 Correct 42 ms 63024 KB Output is correct
31 Correct 55 ms 63024 KB Output is correct
32 Correct 25 ms 62820 KB Output is correct
33 Correct 88 ms 67724 KB Output is correct
34 Correct 116 ms 71340 KB Output is correct
35 Correct 83 ms 72012 KB Output is correct
36 Correct 119 ms 71344 KB Output is correct
37 Correct 160 ms 71764 KB Output is correct
38 Correct 114 ms 72076 KB Output is correct
39 Correct 25 ms 62920 KB Output is correct
40 Correct 26 ms 62928 KB Output is correct
41 Correct 24 ms 62928 KB Output is correct
42 Correct 277 ms 66960 KB Output is correct
43 Correct 923 ms 71328 KB Output is correct
44 Correct 621 ms 64604 KB Output is correct
45 Correct 796 ms 71328 KB Output is correct
46 Correct 568 ms 66216 KB Output is correct
47 Correct 798 ms 71320 KB Output is correct
48 Correct 941 ms 72132 KB Output is correct
49 Correct 1049 ms 72064 KB Output is correct
50 Correct 1081 ms 72116 KB Output is correct
51 Correct 930 ms 71328 KB Output is correct
52 Correct 1133 ms 71760 KB Output is correct
53 Correct 922 ms 72096 KB Output is correct
54 Correct 837 ms 72116 KB Output is correct
55 Correct 24 ms 62820 KB Output is correct
56 Incorrect 169 ms 71352 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62876 KB Output is correct
2 Correct 24 ms 62880 KB Output is correct
3 Correct 181 ms 70672 KB Output is correct
4 Correct 994 ms 72084 KB Output is correct
5 Correct 958 ms 67724 KB Output is correct
6 Correct 1160 ms 72084 KB Output is correct
7 Correct 919 ms 69868 KB Output is correct
8 Correct 1156 ms 72116 KB Output is correct
9 Correct 25 ms 62924 KB Output is correct
10 Correct 26 ms 62932 KB Output is correct
11 Correct 30 ms 62884 KB Output is correct
12 Correct 26 ms 62888 KB Output is correct
13 Incorrect 25 ms 62888 KB Output isn't correct
14 Halted 0 ms 0 KB -