oj.uz

Submission #559009

# Submission time Handle Problem Language Result Execution time Memory
559009 2022-05-09T07:38:29 Z LastRonin Rainforest Jumps (APIO21_jumps) C++14
48 / 100
 1460 ms 47864 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;
    ll Y = C;
    for(int j = 17; j >= 0; j--) { 
		if(bp2[Y][j] == 0)continue;
		if(z[bp2[Y][j]] <= D) {
			Y = z[bp2[Y][j]];
		}
    }
	D = Y;

	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 = z[Le[B]];
	if(C <= z[Le[B]] && z[Le[B]] <= D) return 1;
	if(F >= A && z[Ri[F]] <= D && z[Ri[F]] >= C)return 1;
	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]];
		}
	}
	return cnt;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 194 ms 37616 KB Output is correct
4 Correct 1195 ms 47372 KB Output is correct
5 Correct 928 ms 24124 KB Output is correct
6 Correct 1408 ms 47288 KB Output is correct
7 Correct 1084 ms 32432 KB Output is correct
8 Correct 1460 ms 47316 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 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 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 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 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Incorrect 3 ms 336 KB Output isn't correct
14 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 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 120 ms 38112 KB Output is correct
6 Correct 164 ms 47264 KB Output is correct
7 Correct 77 ms 24368 KB Output is correct
8 Correct 161 ms 47220 KB Output is correct
9 Correct 16 ms 7404 KB Output is correct
10 Correct 169 ms 47260 KB Output is correct
11 Correct 101 ms 47288 KB Output is correct
12 Correct 84 ms 47524 KB Output is correct
13 Incorrect 76 ms 47232 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 238 ms 21808 KB Output is correct
5 Correct 955 ms 47296 KB Output is correct
6 Correct 575 ms 8016 KB Output is correct
7 Correct 1041 ms 47276 KB Output is correct
8 Correct 559 ms 16492 KB Output is correct
9 Correct 1099 ms 47152 KB Output is correct
10 Correct 1207 ms 47268 KB Output is correct
11 Correct 1345 ms 47852 KB Output is correct
12 Correct 1093 ms 47236 KB Output is correct
13 Correct 958 ms 47264 KB Output is correct
14 Correct 1191 ms 47684 KB Output is correct
15 Correct 936 ms 47368 KB Output is correct
16 Correct 861 ms 47348 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 18 ms 720 KB Output is correct
28 Correct 27 ms 720 KB Output is correct
29 Correct 18 ms 720 KB Output is correct
30 Correct 19 ms 720 KB Output is correct
31 Correct 11 ms 720 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 93 ms 27516 KB Output is correct
34 Correct 145 ms 47264 KB Output is correct
35 Correct 114 ms 47236 KB Output is correct
36 Correct 154 ms 47268 KB Output is correct
37 Correct 133 ms 47660 KB Output is correct
38 Correct 112 ms 47428 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 238 ms 21808 KB Output is correct
5 Correct 955 ms 47296 KB Output is correct
6 Correct 575 ms 8016 KB Output is correct
7 Correct 1041 ms 47276 KB Output is correct
8 Correct 559 ms 16492 KB Output is correct
9 Correct 1099 ms 47152 KB Output is correct
10 Correct 1207 ms 47268 KB Output is correct
11 Correct 1345 ms 47852 KB Output is correct
12 Correct 1093 ms 47236 KB Output is correct
13 Correct 958 ms 47264 KB Output is correct
14 Correct 1191 ms 47684 KB Output is correct
15 Correct 936 ms 47368 KB Output is correct
16 Correct 861 ms 47348 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 18 ms 720 KB Output is correct
28 Correct 27 ms 720 KB Output is correct
29 Correct 18 ms 720 KB Output is correct
30 Correct 19 ms 720 KB Output is correct
31 Correct 11 ms 720 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 93 ms 27516 KB Output is correct
34 Correct 145 ms 47264 KB Output is correct
35 Correct 114 ms 47236 KB Output is correct
36 Correct 154 ms 47268 KB Output is correct
37 Correct 133 ms 47660 KB Output is correct
38 Correct 112 ms 47428 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 265 ms 21712 KB Output is correct
43 Correct 1131 ms 47260 KB Output is correct
44 Correct 580 ms 8016 KB Output is correct
45 Correct 800 ms 47260 KB Output is correct
46 Correct 549 ms 16484 KB Output is correct
47 Correct 1127 ms 47260 KB Output is correct
48 Correct 1410 ms 47292 KB Output is correct
49 Correct 1050 ms 47864 KB Output is correct
50 Correct 1268 ms 47304 KB Output is correct
51 Correct 929 ms 47140 KB Output is correct
52 Correct 969 ms 47640 KB Output is correct
53 Correct 910 ms 47332 KB Output is correct
54 Correct 916 ms 47280 KB Output is correct
55 Correct 0 ms 336 KB Output is correct
56 Correct 176 ms 47164 KB Output is correct
57 Correct 851 ms 47132 KB Output is correct
58 Correct 457 ms 8528 KB Output is correct
59 Correct 900 ms 47260 KB Output is correct
60 Correct 350 ms 16896 KB Output is correct
61 Correct 633 ms 47236 KB Output is correct
62 Correct 1045 ms 47268 KB Output is correct
63 Correct 935 ms 47536 KB Output is correct
64 Correct 1058 ms 47304 KB Output is correct
65 Correct 861 ms 47176 KB Output is correct
66 Correct 967 ms 47588 KB Output is correct
67 Correct 888 ms 47796 KB Output is correct
68 Correct 739 ms 47276 KB Output is correct
69 Correct 0 ms 336 KB Output is correct
70 Correct 1 ms 336 KB Output is correct
71 Correct 2 ms 336 KB Output is correct
72 Correct 2 ms 336 KB Output is correct
73 Correct 3 ms 336 KB Output is correct
74 Correct 3 ms 336 KB Output is correct
75 Correct 2 ms 336 KB Output is correct
76 Correct 0 ms 336 KB Output is correct
77 Correct 0 ms 208 KB Output is correct
78 Correct 1 ms 336 KB Output is correct
79 Correct 2 ms 336 KB Output is correct
80 Correct 3 ms 336 KB Output is correct
81 Correct 3 ms 336 KB Output is correct
82 Correct 3 ms 336 KB Output is correct
83 Correct 1 ms 336 KB Output is correct
84 Correct 0 ms 336 KB Output is correct
85 Correct 5 ms 336 KB Output is correct
86 Correct 18 ms 720 KB Output is correct
87 Correct 18 ms 720 KB Output is correct
88 Correct 17 ms 720 KB Output is correct
89 Correct 18 ms 720 KB Output is correct
90 Correct 9 ms 720 KB Output is correct
91 Correct 1 ms 336 KB Output is correct
92 Correct 1 ms 464 KB Output is correct
93 Correct 21 ms 720 KB Output is correct
94 Correct 19 ms 720 KB Output is correct
95 Correct 17 ms 720 KB Output is correct
96 Correct 19 ms 720 KB Output is correct
97 Correct 17 ms 720 KB Output is correct
98 Correct 0 ms 336 KB Output is correct
99 Correct 141 ms 47192 KB Output is correct
100 Correct 132 ms 47228 KB Output is correct
101 Correct 78 ms 47252 KB Output is correct
102 Correct 131 ms 47196 KB Output is correct
103 Correct 108 ms 47684 KB Output is correct
104 Correct 77 ms 47396 KB Output is correct
105 Correct 1 ms 336 KB Output is correct
106 Correct 91 ms 27516 KB Output is correct
107 Correct 169 ms 47284 KB Output is correct
108 Correct 104 ms 47264 KB Output is correct
109 Correct 125 ms 47268 KB Output is correct
110 Correct 127 ms 47648 KB Output is correct
111 Correct 91 ms 47432 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 194 ms 37616 KB Output is correct
4 Correct 1195 ms 47372 KB Output is correct
5 Correct 928 ms 24124 KB Output is correct
6 Correct 1408 ms 47288 KB Output is correct
7 Correct 1084 ms 32432 KB Output is correct
8 Correct 1460 ms 47316 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 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 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Incorrect 3 ms 336 KB Output isn't correct
22 Halted 0 ms 0 KB -