oj.uz

Submission #569501

# Submission time Handle Problem Language Result Execution time Memory
569501 2022-05-27T12:45:42 Z S2speed Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1209 ms 72248 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){
	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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62928 KB Output is correct
2 Correct 27 ms 62844 KB Output is correct
3 Correct 203 ms 70696 KB Output is correct
4 Correct 1153 ms 72164 KB Output is correct
5 Correct 925 ms 67616 KB Output is correct
6 Correct 1093 ms 72156 KB Output is correct
7 Correct 896 ms 69924 KB Output is correct
8 Correct 1209 ms 72164 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62864 KB Output is correct
2 Correct 24 ms 62888 KB Output is correct
3 Correct 23 ms 62908 KB Output is correct
4 Correct 23 ms 62932 KB Output is correct
5 Incorrect 29 ms 62944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62864 KB Output is correct
2 Correct 24 ms 62888 KB Output is correct
3 Correct 23 ms 62908 KB Output is correct
4 Correct 23 ms 62932 KB Output is correct
5 Incorrect 29 ms 62944 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 62920 KB Output is correct
2 Correct 24 ms 62924 KB Output is correct
3 Correct 26 ms 62820 KB Output is correct
4 Correct 27 ms 62936 KB Output is correct
5 Correct 96 ms 70164 KB Output is correct
6 Correct 138 ms 71364 KB Output is correct
7 Correct 66 ms 67180 KB Output is correct
8 Correct 126 ms 71368 KB Output is correct
9 Correct 38 ms 64140 KB Output is correct
10 Correct 128 ms 71368 KB Output is correct
11 Correct 85 ms 72168 KB Output is correct
12 Incorrect 102 ms 71948 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 62936 KB Output is correct
2 Correct 24 ms 62904 KB Output is correct
3 Correct 25 ms 62824 KB Output is correct
4 Correct 285 ms 66872 KB Output is correct
5 Correct 1029 ms 71368 KB Output is correct
6 Correct 658 ms 64580 KB Output is correct
7 Correct 810 ms 71324 KB Output is correct
8 Correct 557 ms 66208 KB Output is correct
9 Correct 890 ms 71328 KB Output is correct
10 Correct 1022 ms 72084 KB Output is correct
11 Correct 1066 ms 72096 KB Output is correct
12 Correct 1175 ms 72016 KB Output is correct
13 Correct 861 ms 71348 KB Output is correct
14 Correct 1184 ms 71772 KB Output is correct
15 Correct 900 ms 72104 KB Output is correct
16 Correct 858 ms 72164 KB Output is correct
17 Correct 26 ms 62936 KB Output is correct
18 Correct 28 ms 62868 KB Output is correct
19 Correct 29 ms 62940 KB Output is correct
20 Correct 28 ms 62928 KB Output is correct
21 Correct 32 ms 62908 KB Output is correct
22 Correct 27 ms 62928 KB Output is correct
23 Correct 27 ms 62864 KB Output is correct
24 Correct 27 ms 62940 KB Output is correct
25 Correct 25 ms 62816 KB Output is correct
26 Correct 24 ms 62932 KB Output is correct
27 Correct 34 ms 63016 KB Output is correct
28 Correct 48 ms 63076 KB Output is correct
29 Correct 49 ms 63024 KB Output is correct
30 Correct 45 ms 62948 KB Output is correct
31 Correct 43 ms 63032 KB Output is correct
32 Correct 24 ms 62892 KB Output is correct
33 Correct 80 ms 67624 KB Output is correct
34 Correct 114 ms 71440 KB Output is correct
35 Correct 84 ms 72044 KB Output is correct
36 Correct 124 ms 71348 KB Output is correct
37 Correct 159 ms 71764 KB Output is correct
38 Correct 90 ms 72248 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62936 KB Output is correct
2 Correct 24 ms 62904 KB Output is correct
3 Correct 25 ms 62824 KB Output is correct
4 Correct 285 ms 66872 KB Output is correct
5 Correct 1029 ms 71368 KB Output is correct
6 Correct 658 ms 64580 KB Output is correct
7 Correct 810 ms 71324 KB Output is correct
8 Correct 557 ms 66208 KB Output is correct
9 Correct 890 ms 71328 KB Output is correct
10 Correct 1022 ms 72084 KB Output is correct
11 Correct 1066 ms 72096 KB Output is correct
12 Correct 1175 ms 72016 KB Output is correct
13 Correct 861 ms 71348 KB Output is correct
14 Correct 1184 ms 71772 KB Output is correct
15 Correct 900 ms 72104 KB Output is correct
16 Correct 858 ms 72164 KB Output is correct
17 Correct 26 ms 62936 KB Output is correct
18 Correct 28 ms 62868 KB Output is correct
19 Correct 29 ms 62940 KB Output is correct
20 Correct 28 ms 62928 KB Output is correct
21 Correct 32 ms 62908 KB Output is correct
22 Correct 27 ms 62928 KB Output is correct
23 Correct 27 ms 62864 KB Output is correct
24 Correct 27 ms 62940 KB Output is correct
25 Correct 25 ms 62816 KB Output is correct
26 Correct 24 ms 62932 KB Output is correct
27 Correct 34 ms 63016 KB Output is correct
28 Correct 48 ms 63076 KB Output is correct
29 Correct 49 ms 63024 KB Output is correct
30 Correct 45 ms 62948 KB Output is correct
31 Correct 43 ms 63032 KB Output is correct
32 Correct 24 ms 62892 KB Output is correct
33 Correct 80 ms 67624 KB Output is correct
34 Correct 114 ms 71440 KB Output is correct
35 Correct 84 ms 72044 KB Output is correct
36 Correct 124 ms 71348 KB Output is correct
37 Correct 159 ms 71764 KB Output is correct
38 Correct 90 ms 72248 KB Output is correct
39 Correct 27 ms 62872 KB Output is correct
40 Correct 27 ms 62928 KB Output is correct
41 Correct 29 ms 62836 KB Output is correct
42 Correct 241 ms 66836 KB Output is correct
43 Correct 1000 ms 71324 KB Output is correct
44 Correct 483 ms 64548 KB Output is correct
45 Correct 925 ms 71372 KB Output is correct
46 Correct 526 ms 66236 KB Output is correct
47 Correct 967 ms 71300 KB Output is correct
48 Correct 1203 ms 72112 KB Output is correct
49 Correct 988 ms 72096 KB Output is correct
50 Correct 1112 ms 72148 KB Output is correct
51 Correct 893 ms 71352 KB Output is correct
52 Correct 1118 ms 71712 KB Output is correct
53 Correct 937 ms 72128 KB Output is correct
54 Correct 798 ms 72120 KB Output is correct
55 Correct 24 ms 62912 KB Output is correct
56 Incorrect 173 ms 71316 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62928 KB Output is correct
2 Correct 27 ms 62844 KB Output is correct
3 Correct 203 ms 70696 KB Output is correct
4 Correct 1153 ms 72164 KB Output is correct
5 Correct 925 ms 67616 KB Output is correct
6 Correct 1093 ms 72156 KB Output is correct
7 Correct 896 ms 69924 KB Output is correct
8 Correct 1209 ms 72164 KB Output is correct
9 Correct 26 ms 62864 KB Output is correct
10 Correct 24 ms 62888 KB Output is correct
11 Correct 23 ms 62908 KB Output is correct
12 Correct 23 ms 62932 KB Output is correct
13 Incorrect 29 ms 62944 KB Output isn't correct
14 Halted 0 ms 0 KB -