oj.uz

Submission #558995

# Submission time Handle Problem Language Result Execution time Memory
558995 2022-05-09T07:16:56 Z LastRonin Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1141 ms 47844 KB 
#include "jumps.h"
 
#include <bits/stdc++.h>
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
using namespace std;
 
const int N = 2e5 + 10;
 
int bp[N][18];
int bp2[N][18];
int bp3[N][18];
int z[N], h[N];
int Le[N], Ri[N];
 
void init(int n, vector<int> H) {
	for(int j = 1; j <= n; j++)
		h[j] = H[j - 1];
    stack<int> L, R;
	for(int j = 1; j <= n; j++)
		z[h[j]] = j;
	for(int i = 1; i <= n; i++) {
		while(L.size() && L.top() <= h[i])L.pop();	
		if(L.size())
			Le[i] = L.top();
		L.push(h[i]);		
	}	
	for(int i = n; i >= 1; i--) {
		while(R.size() && R.top() <= h[i])R.pop();	
		if(R.size())
			Ri[i] = R.top();
		R.push(h[i]);		
	}
	for(int j = n; j >= 1; j--) {
		bp[z[j]][0] = (Le[z[j]] > Ri[z[j]] ? Le[z[j]] : Ri[z[j]]);
		bp2[z[j]][0] = Ri[z[j]];
		bp3[z[j]][0] = Le[z[j]];
		for(int i = 1; i < 18; i++) {
			bp[z[j]][i] = bp[z[bp[z[j]][i - 1]]][i - 1];
			bp2[z[j]][i] = bp2[z[bp2[z[j]][i - 1]]][i - 1];
			bp3[z[j]][i] = bp3[z[bp3[z[j]][i - 1]]][i - 1];
		}
	}	
}
 
int minimum_jumps(int A, int B, int C, int D) {	
	A++, B++, C++, D++;
	ll X = B;
	for(int j = 17; j >= 0; j--) {
		if(bp2[X][j] == 0)continue;
		if(z[bp2[X][j]] < C) {
			X = z[bp2[X][j]];
		}
	}
	X = z[bp2[X][0]];	
	if(X > D || X == 0)return -1;
	C = X;

	for(int j = 17; j >= 0; j--) {
		if(bp3[B][j] == 0)continue;
		if(bp3[B][j] <= h[C] && z[bp3[B][j]] >= A) {
			B = z[bp3[B][j]];
		}		
	}
	ll F = Le[B];
	if(F >= A && Ri[F] <= D && Ri[F] >= C)return 1;
	ll mnans = N + 1;
	if(F != 0 && Ri[F] <= D && Ri[F] >= C) mnans = 2; 
	ll cnt = 0;
	for(int j = 17; j >= 0; j--) {
		if(bp[B][j] == 0)continue;
		if(bp[B][j] <= h[C]) {
			cnt += (1<<j);
			B = z[bp[B][j]];
		}
	}
	for(int j = 17; j >= 0; j--) {
		if(bp2[B][j] == 0)continue;
		if(bp2[B][j] <= h[C]) {
			cnt += (1<<j);
			B = z[bp2[B][j]];
		}
	}
	if(B != C)return -1;
	return min(mnans, cnt);
}

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 160 ms 37612 KB Output is correct
4 Correct 1066 ms 47260 KB Output is correct
5 Correct 1043 ms 23868 KB Output is correct
6 Correct 1081 ms 47240 KB Output is correct
7 Correct 781 ms 32340 KB Output is correct
8 Correct 1141 ms 47296 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 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 0 ms 292 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 216 ms 21768 KB Output is correct
5 Correct 772 ms 47176 KB Output is correct
6 Correct 415 ms 8084 KB Output is correct
7 Correct 934 ms 47284 KB Output is correct
8 Correct 482 ms 16452 KB Output is correct
9 Correct 847 ms 47256 KB Output is correct
10 Correct 992 ms 47224 KB Output is correct
11 Incorrect 1012 ms 47844 KB Output isn't correct
12 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 0 ms 292 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 216 ms 21768 KB Output is correct
5 Correct 772 ms 47176 KB Output is correct
6 Correct 415 ms 8084 KB Output is correct
7 Correct 934 ms 47284 KB Output is correct
8 Correct 482 ms 16452 KB Output is correct
9 Correct 847 ms 47256 KB Output is correct
10 Correct 992 ms 47224 KB Output is correct
11 Incorrect 1012 ms 47844 KB Output isn't correct
12 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 160 ms 37612 KB Output is correct
4 Correct 1066 ms 47260 KB Output is correct
5 Correct 1043 ms 23868 KB Output is correct
6 Correct 1081 ms 47240 KB Output is correct
7 Correct 781 ms 32340 KB Output is correct
8 Correct 1141 ms 47296 KB Output is correct
9 Incorrect 0 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -