oj.uz

Submission #515135

# Submission time Handle Problem Language Result Execution time Memory
515135 2022-01-19T03:47:58 Z minhcool Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1108 ms 68468 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 || a > b) 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 1 ms 344 KB Output is correct
3 Correct 200 ms 54560 KB Output is correct
4 Correct 1066 ms 68468 KB Output is correct
5 Correct 926 ms 34616 KB Output is correct
6 Correct 1108 ms 68416 KB Output is correct
7 Correct 831 ms 46780 KB Output is correct
8 Correct 1045 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 1 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 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 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 0 ms 328 KB Output is correct
5 Correct 120 ms 54480 KB Output is correct
6 Correct 130 ms 67520 KB Output is correct
7 Correct 61 ms 34716 KB Output is correct
8 Correct 128 ms 67636 KB Output is correct
9 Correct 11 ms 10440 KB Output is correct
10 Correct 137 ms 67520 KB Output is correct
11 Correct 122 ms 68460 KB Output is correct
12 Correct 123 ms 68252 KB Output is correct
13 Correct 134 ms 68144 KB Output is correct
14 Correct 134 ms 67608 KB Output is correct
15 Incorrect 152 ms 68072 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 263 ms 31060 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 263 ms 31060 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 1 ms 344 KB Output is correct
3 Correct 200 ms 54560 KB Output is correct
4 Correct 1066 ms 68468 KB Output is correct
5 Correct 926 ms 34616 KB Output is correct
6 Correct 1108 ms 68416 KB Output is correct
7 Correct 831 ms 46780 KB Output is correct
8 Correct 1045 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 1 ms 328 KB Output is correct
13 Runtime error 3 ms 456 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -