oj.uz

Submission #515124

# Submission time Handle Problem Language Result Execution time Memory
515124 2022-01-19T03:42:01 Z minhcool Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1513 ms 68476 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[temp2.fi]) 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);
	}
    if(c == d){
		assert(answer >= cal2(a, b, c));
    }
	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 1 ms 328 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 245 ms 54552 KB Output is correct
4 Correct 1123 ms 68376 KB Output is correct
5 Correct 1207 ms 34712 KB Output is correct
6 Correct 1513 ms 68476 KB Output is correct
7 Correct 983 ms 46792 KB Output is correct
8 Correct 1407 ms 68436 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Runtime error 3 ms 456 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Runtime error 3 ms 456 KB Execution killed with signal 6
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 115 ms 54476 KB Output is correct
6 Correct 146 ms 67644 KB Output is correct
7 Correct 83 ms 34788 KB Output is correct
8 Correct 162 ms 67636 KB Output is correct
9 Correct 12 ms 10440 KB Output is correct
10 Correct 169 ms 67648 KB Output is correct
11 Correct 152 ms 68464 KB Output is correct
12 Correct 125 ms 68144 KB Output is correct
13 Correct 132 ms 68228 KB Output is correct
14 Correct 130 ms 67620 KB Output is correct
15 Incorrect 155 ms 68004 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 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 113 ms 62108 KB Execution killed with signal 6
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 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Runtime error 113 ms 62108 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 245 ms 54552 KB Output is correct
4 Correct 1123 ms 68376 KB Output is correct
5 Correct 1207 ms 34712 KB Output is correct
6 Correct 1513 ms 68476 KB Output is correct
7 Correct 983 ms 46792 KB Output is correct
8 Correct 1407 ms 68436 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Runtime error 3 ms 456 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -