oj.uz

Submission #515131

# Submission time Handle Problem Language Result Execution time Memory
515131 2022-01-19T03:45:12 Z minhcool Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1233 ms 68472 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(c == d){
        assert(answer >= cal2(a, b, c));
    }
	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 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 205 ms 54516 KB Output is correct
4 Correct 1058 ms 68464 KB Output is correct
5 Correct 1067 ms 34624 KB Output is correct
6 Correct 1233 ms 68420 KB Output is correct
7 Correct 1000 ms 46872 KB Output is correct
8 Correct 1072 ms 68416 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 0 ms 328 KB Output is correct
5 Runtime error 2 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 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 0 ms 328 KB Output is correct
5 Runtime error 2 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 0 ms 328 KB Output is correct
5 Correct 119 ms 54416 KB Output is correct
6 Correct 124 ms 67648 KB Output is correct
7 Correct 67 ms 34788 KB Output is correct
8 Correct 128 ms 67532 KB Output is correct
9 Correct 11 ms 10440 KB Output is correct
10 Correct 123 ms 67612 KB Output is correct
11 Correct 117 ms 68472 KB Output is correct
12 Correct 137 ms 68184 KB Output is correct
13 Correct 130 ms 68364 KB Output is correct
14 Correct 122 ms 67556 KB Output is correct
15 Incorrect 139 ms 68000 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 275 ms 30988 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 275 ms 30988 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 205 ms 54516 KB Output is correct
4 Correct 1058 ms 68464 KB Output is correct
5 Correct 1067 ms 34624 KB Output is correct
6 Correct 1233 ms 68420 KB Output is correct
7 Correct 1000 ms 46872 KB Output is correct
8 Correct 1072 ms 68416 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 0 ms 328 KB Output is correct
13 Runtime error 2 ms 456 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -