oj.uz

Submission #972414

# Submission time Handle Problem Language Result Execution time Memory
972414 2024-04-30T11:49:57 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
23 / 100
 910 ms 35528 KB 
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;

// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;

const int inf = 1e9 + 9;
const int mxn = 2e5 + 5;
const int mod = 1e9 + 7;

int n;
int h[mxn] , le[mxn] , ri[mxn];
int inv[mxn];
int spx[19][mxn] , spn[19][mxn];

vint v;

void init(int N , vint H) {
	n = N;
	for (int i = 0; i < n; i++) {
		h[i] = H[i];
		inv[h[i]] = i;
	}

	for (int i = 0; i < n; i++) {
		while (v.size() > 0 && v.back() < h[i]) {
			ri[v.back()] = h[i];
			v.pop_back();
		}
		if (v.size() > 0) le[h[i]] = v.back();
		v.push_back(h[i]);
	}

	for (int i = 0; i < n; i++) {
		spx[0][h[i]] = max(le[h[i]] , ri[h[i]]);
		spn[0][h[i]] = min(le[h[i]] , ri[h[i]]);
		if (spn[0][h[i]] == 0) spn[0][h[i]] = spx[0][h[i]];
	}

	for (int j = 1; j < 19; j++) {
		for (int i = 0; i < n; i++) {
			spx[j][h[i]] = spx[j-1][spx[j-1][h[i]]];
			spn[j][h[i]] = spn[j-1][spn[j-1][h[i]]];
		}
	}
}

int minimum_jumps(int a , int b , int c , int d) {
	if (h[a] > h[d]) return -1;
	int dis = 0;
	for (int i = 18; i >= 0; i--) {
		if (spx[i][h[a]] > h[d] || spx[i][h[a]] == 0) continue;
		if (spx[i][h[a]] == h[d]) return (1 << i);
		int t = minimum_jumps(inv[spx[i][h[a]]] , b , c , d);
		return (t == -1) ? t : ((1<<i) + t);
	}

	for (int i = 18; i >= 0; i--) {
		if (spn[i][h[a]] > h[d] || spn[i][h[a]] == 0) continue;
		if (spn[i][h[a]] == h[d]) return (1 << i);
		int t = minimum_jumps(inv[spn[i][h[a]]] , b , c , d);
		return (t == -1) ? t : ((1<<i) + t);
	}

	return -1;
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:56:6: warning: unused variable 'dis' [-Wunused-variable]
   56 |  int dis = 0;
      |      ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Incorrect 86 ms 33308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

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

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 4 ms 31072 KB Output is correct
3 Correct 3 ms 31064 KB Output is correct
4 Correct 144 ms 32808 KB Output is correct
5 Correct 652 ms 34644 KB Output is correct
6 Correct 432 ms 31824 KB Output is correct
7 Correct 630 ms 34772 KB Output is correct
8 Correct 424 ms 32480 KB Output is correct
9 Correct 683 ms 34752 KB Output is correct
10 Correct 735 ms 34000 KB Output is correct
11 Correct 849 ms 34512 KB Output is correct
12 Correct 741 ms 34008 KB Output is correct
13 Correct 702 ms 34776 KB Output is correct
14 Correct 694 ms 35384 KB Output is correct
15 Correct 521 ms 35396 KB Output is correct
16 Correct 547 ms 35396 KB Output is correct
17 Correct 4 ms 31064 KB Output is correct
18 Correct 4 ms 31064 KB Output is correct
19 Correct 4 ms 31064 KB Output is correct
20 Correct 5 ms 31064 KB Output is correct
21 Correct 5 ms 31064 KB Output is correct
22 Correct 5 ms 31064 KB Output is correct
23 Correct 4 ms 31064 KB Output is correct
24 Correct 6 ms 31064 KB Output is correct
25 Correct 4 ms 31192 KB Output is correct
26 Correct 4 ms 31076 KB Output is correct
27 Correct 17 ms 31072 KB Output is correct
28 Correct 13 ms 31076 KB Output is correct
29 Correct 13 ms 31076 KB Output is correct
30 Correct 14 ms 31072 KB Output is correct
31 Correct 13 ms 31072 KB Output is correct
32 Correct 4 ms 31064 KB Output is correct
33 Correct 21 ms 33168 KB Output is correct
34 Correct 36 ms 34776 KB Output is correct
35 Correct 24 ms 34016 KB Output is correct
36 Correct 33 ms 34776 KB Output is correct
37 Correct 30 ms 35496 KB Output is correct
38 Correct 25 ms 35412 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 4 ms 31072 KB Output is correct
3 Correct 3 ms 31064 KB Output is correct
4 Correct 144 ms 32808 KB Output is correct
5 Correct 652 ms 34644 KB Output is correct
6 Correct 432 ms 31824 KB Output is correct
7 Correct 630 ms 34772 KB Output is correct
8 Correct 424 ms 32480 KB Output is correct
9 Correct 683 ms 34752 KB Output is correct
10 Correct 735 ms 34000 KB Output is correct
11 Correct 849 ms 34512 KB Output is correct
12 Correct 741 ms 34008 KB Output is correct
13 Correct 702 ms 34776 KB Output is correct
14 Correct 694 ms 35384 KB Output is correct
15 Correct 521 ms 35396 KB Output is correct
16 Correct 547 ms 35396 KB Output is correct
17 Correct 4 ms 31064 KB Output is correct
18 Correct 4 ms 31064 KB Output is correct
19 Correct 4 ms 31064 KB Output is correct
20 Correct 5 ms 31064 KB Output is correct
21 Correct 5 ms 31064 KB Output is correct
22 Correct 5 ms 31064 KB Output is correct
23 Correct 4 ms 31064 KB Output is correct
24 Correct 6 ms 31064 KB Output is correct
25 Correct 4 ms 31192 KB Output is correct
26 Correct 4 ms 31076 KB Output is correct
27 Correct 17 ms 31072 KB Output is correct
28 Correct 13 ms 31076 KB Output is correct
29 Correct 13 ms 31076 KB Output is correct
30 Correct 14 ms 31072 KB Output is correct
31 Correct 13 ms 31072 KB Output is correct
32 Correct 4 ms 31064 KB Output is correct
33 Correct 21 ms 33168 KB Output is correct
34 Correct 36 ms 34776 KB Output is correct
35 Correct 24 ms 34016 KB Output is correct
36 Correct 33 ms 34776 KB Output is correct
37 Correct 30 ms 35496 KB Output is correct
38 Correct 25 ms 35412 KB Output is correct
39 Correct 4 ms 31076 KB Output is correct
40 Correct 4 ms 31072 KB Output is correct
41 Correct 4 ms 31076 KB Output is correct
42 Correct 164 ms 32840 KB Output is correct
43 Correct 664 ms 34656 KB Output is correct
44 Correct 445 ms 31824 KB Output is correct
45 Correct 670 ms 34752 KB Output is correct
46 Correct 408 ms 32344 KB Output is correct
47 Correct 686 ms 34756 KB Output is correct
48 Correct 787 ms 33976 KB Output is correct
49 Correct 910 ms 34640 KB Output is correct
50 Correct 689 ms 34004 KB Output is correct
51 Correct 686 ms 34756 KB Output is correct
52 Correct 751 ms 35392 KB Output is correct
53 Correct 581 ms 35444 KB Output is correct
54 Correct 575 ms 35528 KB Output is correct
55 Correct 4 ms 31064 KB Output is correct
56 Incorrect 63 ms 34752 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Incorrect 86 ms 33308 KB Output isn't correct
4 Halted 0 ms 0 KB -