oj.uz

Submission #552771

# Submission time Handle Problem Language Result Execution time Memory
552771 2022-04-23T20:45:50 Z QwertyPi Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1234 ms 83488 KB 
#include "jumps.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 200002;
const int inf = 1 << 20;
int mx[N][20], h[N], pl[N], pr[N], p[N];
int bl[N][20], bl_r[N][20];
int n;

void mx_prec(){
	for(int i = 1; i <= n; i++){
		mx[i][0] = h[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 1; i <= n + 1 - (1 << j); i++){
			mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
		}
	}
}

void bl_prec(){
	bl[0][0] = 0, bl[n + 1][0] = n + 1;
	for(int i = 1; i <= n; i++){
		bl[i][0] = p[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i <= n + 1; i++){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	bl_r[0][0] = 0, bl_r[n + 1][0] = n + 1;
	for(int i = 1; i <= n; i++){
		bl_r[i][0] = pr[i];
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i <= n + 1; i++){
			bl_r[i][j] = bl_r[bl_r[i][j - 1]][j - 1];
		}
	}
}

int mx_qry(int l, int r){
	if(l <= 0 || r >= n + 1 || l > r + 1) return inf;
	if(l == r + 1) return 0;
	int d = __lg(r - l + 1);
	return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}

void init(int N, std::vector<int> H) {
	::n = N;
	for(int i = 1; i <= N; i++){
		h[i] = H[i - 1];
	}
	h[0] = h[n + 1] = inf;
	pl[0] = 0, pr[0] = 0, pl[n + 1] = n + 1, pr[n + 1] = n + 1;
	vector<pii> L {{inf, 0}};
	for(int i = 1; i <= n; i++){
		while(L.back().fi < h[i]) L.pop_back();
		pl[i] = L.back().se;
		L.push_back({h[i], i});
	}
	vector<pii> R {{inf, n + 1}};
	for(int i = n; i >= 1; i--){
		while(R.back().fi < h[i]) R.pop_back();
		pr[i] = R.back().se;
		R.push_back({h[i], i});
	}
	p[0] = 0, p[n + 1] = n + 1;
	for(int i = 1; i <= n; i++){
		if(h[pl[i]] == inf || h[pr[i]] == inf) p[i] = h[pl[i]] != inf ? pl[i] : pr[i];
		else p[i] = h[pl[i]] < h[pr[i]] ? pr[i] : pl[i];
	}
	mx_prec();
	bl_prec();
}

int minimum_jumps(int A, int B, int C, int D) {
	A++; B++; C++; D++;
	if(mx_qry(B, C - 1) > mx_qry(C, D)) return -1;
	int mx_CD = mx_qry(C, D);
	int mx_gap = mx_qry(B + 1, C - 1);
	int mx_val_AB = inf, mx_idx_AB = -1;
	{
		int l = 1, r = B - A + 1;
		while(l != r){
			int m = (l + r + 1) / 2;
			if(mx_qry(B - m + 1, B) < mx_qry(C, D)){
				l = m;
			}else{
				r = m - 1;
			}
		}
		mx_val_AB = mx_qry(B - l + 1, B);
	}
	if(mx_val_AB == 0) return -1;
	{
		int l = 0, r = B - A + 1;
		while(l != r){
			int m = (l + r + 1) / 2;
			if(mx_qry(B - m + 1, B) < mx_val_AB){
				l = m;
			}else{
				r = m - 1;
			}
		}
		mx_idx_AB = B - l;
	}
	assert(h[mx_idx_AB] == mx_val_AB);
	int ST = mx_idx_AB;
	assert(ST == B);
	int ans = 0;
	{
		int steps = 0;
		for(int j = 19; j >= 0; j--){
			if(h[bl[ST][j]] < mx_gap) steps += (1 << j), ST = bl[ST][j];
		}
		ans += steps;
	}
	{
		if(h[pl[ST]] < mx_CD && !(C <= pr[ST] && pr[ST] <= D)) ans++, ST = pl[ST];
	}
	{
		int steps = 0;
		for(int j = 19; j >= 0; j--){
			if(bl_r[ST][j] < C) steps += (1 << j), ST = bl_r[ST][j];
		}
		ans += steps;
	}
	{
		if(ST < C) ST = pr[ST], ans++;
		if(C <= ST && ST <= D) return ans;
		else return -1;
	}
}

Compilation message

jumps.cpp: In function 'void mx_prec()':
jumps.cpp:19:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   19 |    mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                              ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 202 ms 42724 KB Output is correct
4 Correct 1234 ms 53540 KB Output is correct
5 Correct 911 ms 27180 KB Output is correct
6 Correct 1101 ms 53620 KB Output is correct
7 Correct 872 ms 36804 KB Output is correct
8 Correct 1123 ms 53628 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Runtime error 2 ms 464 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Runtime error 2 ms 464 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Runtime error 140 ms 83488 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 207 ms 23948 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 207 ms 23948 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 202 ms 42724 KB Output is correct
4 Correct 1234 ms 53540 KB Output is correct
5 Correct 911 ms 27180 KB Output is correct
6 Correct 1101 ms 53620 KB Output is correct
7 Correct 872 ms 36804 KB Output is correct
8 Correct 1123 ms 53628 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Runtime error 2 ms 464 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -