oj.uz

Submission #515111

# Submission time Handle Problem Language Result Execution time Memory
515111 2022-01-19T03:29:17 Z minhcool Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1359 ms 68508 KB 
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
int n, h[N], lg2[N];
 
int nxtl[N], nxtr[N];
 
int small_jump[N][20], large_jump[N][20];
 
ii mx[N][20];
 
void init(int _n, vector<int> _H){
	n = _n;
	for(int i = 1; i <= n; i++) h[i] = _H[i - 1];
	h[0] = h[n + 1] = oo;
	stack<int> stk;
	stk.push(0);
	for(int i = 1; i <= n; i++) lg2[i] = log2(i);
	for(int i = 1; i <= n; i++){
		while(h[stk.top()] < h[i]) stk.pop();
		nxtl[i] = stk.top();
		stk.push(i);
	}
    //return;
	while(!stk.empty()) stk.pop();
	stk.push(n + 1);
	for(int i = n; i >= 1; i--){
		while(h[stk.top()] < h[i]) stk.pop();
		nxtr[i] = stk.top();
		stk.push(i);
	}
    //return;
	for(int i = 1; i <= n; i++){
		small_jump[i][0] = (h[nxtl[i]] < h[nxtr[i]] ? nxtl[i] : nxtr[i]);
		large_jump[i][0] = (h[nxtl[i]] > h[nxtr[i]] ? nxtl[i] : nxtr[i]);
	}
	for(int i = 1; i <= n; i++) mx[i][0] = {h[i], i};
	for(int i = 1; i <= 19; i++){
		for(int j = 1; (j + (1LL << i) - 1) <= n; j++) mx[j][i] = max(mx[j][i - 1], mx[j + (1LL << (i - 1))][i - 1]);
	}
	for(int i = 1; i <= 19; i++){
		for(int j = 1; j <= n; j++){
			small_jump[j][i] = small_jump[small_jump[j][i - 1]][i - 1];
			large_jump[j][i] = large_jump[large_jump[j][i - 1]][i - 1];
		}
	}
}
 
ii maxi(int l, int r){
	if(l > r) return {-oo, -oo};
	int k = lg2[r - l + 1];
	return max(mx[l][k], mx[r - (1LL << k) + 1][k]);
}
 
int cal(int a, int c){
	int answer = 0;
	for(int i = 19; i >= 0; i--){
		if(h[large_jump[a][i]] <= h[c]){
			answer += (1LL << i);
			a = large_jump[a][i];
		}
	}
	for(int i = 19; i >= 0; i--){
		if(h[small_jump[a][i]] <= h[c]){
			answer += (1LL << i);
			a = small_jump[a][i];
		}
	}
	if(a != c) return -1;
	else return answer;
}
 
int cal2(int a, int b, int c){
	//assert(c == d);
	if(h[b] > h[c]){
		return -1;
	}
	int l = a, r = b;
	while(l < r){
		int mid = (l + r) >> 1;
		if(maxi(mid, b).fi > h[c]) l = mid + 1;
		else r = mid;
	}
	int pos = maxi(l, b).se;
	return cal(pos, c);
}
 
int minimum_jumps(int a, int b, int c, int d){
    //return -1;
	a++, b++, c++, d++;
	if(b == (c - 1)){
		if(h[b] > maxi(c, d).fi) return -1;
		else return 1;
	}
	ii temp1 = maxi(a, b), temp2 = maxi(b + 1, c - 1), temp3 = maxi(c, d);
	if(min(temp1.fi, temp3.fi) > temp2.fi){
        //assert(0);
		int l = a, r = b;
		while(l < r){
			int mid = (l + r + 1) >> 1;
			if(maxi(mid, b).fi < h[c]) r = mid - 1;
			else l = mid;
		}
		if(temp3.fi > h[l]) return 1;
		else a = l + 1;
	}
	if(temp3.fi < temp2.fi) return -1;
	int answer = oo;
	answer = min(answer, cal2(a, b, temp2.se) + 1);
	if(a && maxi(1, a - 1).fi > temp2.fi){
		int l = 1, r = a - 1;
		while(l < r){
			int mid = (l + r + 1) >> 1;
			if(maxi(mid, a - 1).fi < h[temp2.fi]) r = mid - 1;
			else l = mid;
		}
		if(h[l] < temp3.fi) answer = min(answer, cal2(a, b, l) + 1);
	}
	return (answer == oo ? -1 : answer);
}
 
/*
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 221 ms 54548 KB Output is correct
4 Correct 1206 ms 68400 KB Output is correct
5 Correct 1154 ms 34652 KB Output is correct
6 Correct 1359 ms 68476 KB Output is correct
7 Correct 983 ms 46784 KB Output is correct
8 Correct 1070 ms 68508 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Incorrect 2 ms 328 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Incorrect 2 ms 328 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 113 ms 54428 KB Output is correct
6 Correct 141 ms 67596 KB Output is correct
7 Correct 70 ms 34700 KB Output is correct
8 Correct 139 ms 67680 KB Output is correct
9 Correct 11 ms 10408 KB Output is correct
10 Correct 146 ms 67640 KB Output is correct
11 Correct 119 ms 68428 KB Output is correct
12 Correct 120 ms 68240 KB Output is correct
13 Correct 135 ms 68232 KB Output is correct
14 Correct 160 ms 67604 KB Output is correct
15 Incorrect 134 ms 67944 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 174 ms 31100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 174 ms 31100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 221 ms 54548 KB Output is correct
4 Correct 1206 ms 68400 KB Output is correct
5 Correct 1154 ms 34652 KB Output is correct
6 Correct 1359 ms 68476 KB Output is correct
7 Correct 983 ms 46784 KB Output is correct
8 Correct 1070 ms 68508 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Incorrect 2 ms 328 KB Output isn't correct
14 Halted 0 ms 0 KB -