oj.uz

Submission #417417

# Submission time Handle Problem Language Result Execution time Memory
417417 2021-06-03T17:06:54 Z CSQ31 Rainforest Jumps (APIO21_jumps) C++14
60 / 100
 1233 ms 51252 KB 
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
const int MAXN = 2e5+5;
int l[20][MAXN],r[20][MAXN],high[20][MAXN];
vector<int>H;
void init(int n, vector<int>h){
	H = h;
	H.insert(H.begin(),1e9);
	H.pb(1e9);
	stack<pii>stk;
	for(int i=0;i<=n+1;i++){
		while(!stk.empty() && stk.top().fi <= H[i])stk.pop();
		if(!stk.empty())l[0][i] = stk.top().se;
		else l[0][i] = i;
		stk.push({H[i],i});
	}
	while(!stk.empty())stk.pop();
	for(int i=n+1;i>=0;i--){
	    while(!stk.empty() && stk.top().fi <= H[i])stk.pop();
		if(!stk.empty())r[0][i] = stk.top().se;
		else r[0][i] = i;
		stk.push({H[i],i});
	}
	for(int i=0;i<=n+1;i++){
		high[0][i] = (H[r[0][i]] > H[l[0][i]])?r[0][i]:l[0][i];
	}
	//cout<<high[0][1]<<'\n';
	for(int j=1;j<20;j++){
		for(int i=0;i<=n+1;i++){
			l[j][i] = l[j-1][l[j-1][i]];
			r[j][i] = r[j-1][r[j-1][i]];
			high[j][i] = high[j-1][high[j-1][i]];
		}
	}
	
}
//
int minimum_jumps(int a,int b,int c,int d){
	a++;
	b++;
	c++;
	d++;
	if(c-1 == b){
		return r[0][b] <=d?1:-1;
	}
	int mid = b+1; //mid just means bigger element in (b,c),cuz we have to cross mid regardless
	for(int i=19;i>=0;i--)if(r[i][mid] < c)mid = r[i][mid];
	if(r[0][mid] > d || r[0][b] > d)return -1;
	int cur = b;
	for(int i=19;i>=0;i--)if(l[i][cur] >= a && H[l[i][cur]] < H[mid])cur = l[i][cur]; //cur is where we should start from
	int ans= 0;
	//if(a == 1)cout<<l[0][cur]<<'\n';
	if(l[0][cur] >= a){
		if(r[0][l[0][cur]] <= d)return 1; //if this case fails it just means we can never ever again go left
	}else{
		for(int i=19;i>=0;i--){
			if(H[high[i][cur]] <= H[mid]){
				cur = high[i][cur];
				ans+=(1<<i);
			}
		}
		//if(a == 1)cout<<cur<<" "<<ans<<'\n';
		if(cur == mid)return r[0][mid] <=d?ans+1:-1;
		else if(high[0][cur] != 0 && r[0][high[0][cur]] <= d)return ans+2; 
	}
	for(int i=19;i>=0;i--){
		if(r[i][cur] < c){
			cur = r[i][cur];
			ans+=(1<<i);
		}
	}
	cur = r[0][cur];
	if(c<=cur && cur<=d)return ans+1;
	else return -1; 
	
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 145 ms 40992 KB Output is correct
4 Correct 1218 ms 51248 KB Output is correct
5 Correct 987 ms 26124 KB Output is correct
6 Correct 1150 ms 51248 KB Output is correct
7 Correct 931 ms 35240 KB Output is correct
8 Correct 1137 ms 51216 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 0 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Incorrect 2 ms 584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 0 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Incorrect 2 ms 584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 54 ms 40204 KB Output is correct
6 Correct 62 ms 49552 KB Output is correct
7 Correct 33 ms 25828 KB Output is correct
8 Correct 60 ms 49548 KB Output is correct
9 Correct 11 ms 8168 KB Output is correct
10 Correct 60 ms 49552 KB Output is correct
11 Correct 56 ms 51224 KB Output is correct
12 Correct 55 ms 50696 KB Output is correct
13 Correct 61 ms 50688 KB Output is correct
14 Correct 58 ms 49548 KB Output is correct
15 Correct 57 ms 50460 KB Output is correct
16 Correct 56 ms 51080 KB Output is correct
17 Correct 56 ms 50972 KB Output is correct
18 Correct 1 ms 712 KB Output is correct
19 Correct 1 ms 584 KB Output is correct
20 Correct 1 ms 584 KB Output is correct
21 Correct 1 ms 584 KB Output is correct
22 Correct 1 ms 584 KB Output is correct
23 Correct 1 ms 584 KB Output is correct
24 Correct 1 ms 584 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 840 KB Output is correct
27 Correct 1 ms 1096 KB Output is correct
28 Correct 1 ms 1096 KB Output is correct
29 Correct 1 ms 1096 KB Output is correct
30 Correct 1 ms 1096 KB Output is correct
31 Correct 1 ms 1096 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 63 ms 49560 KB Output is correct
34 Correct 75 ms 49540 KB Output is correct
35 Correct 55 ms 50824 KB Output is correct
36 Correct 58 ms 49584 KB Output is correct
37 Correct 56 ms 50356 KB Output is correct
38 Correct 71 ms 51216 KB Output is correct
39 Correct 1 ms 584 KB Output is correct
40 Correct 34 ms 29008 KB Output is correct
41 Correct 60 ms 49544 KB Output is correct
42 Correct 59 ms 50992 KB Output is correct
43 Correct 59 ms 49532 KB Output is correct
44 Correct 63 ms 50352 KB Output is correct
45 Correct 56 ms 51248 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 243 ms 23000 KB Output is correct
5 Correct 964 ms 49584 KB Output is correct
6 Correct 517 ms 8644 KB Output is correct
7 Correct 818 ms 49572 KB Output is correct
8 Correct 507 ms 17456 KB Output is correct
9 Correct 945 ms 49584 KB Output is correct
10 Correct 981 ms 51248 KB Output is correct
11 Correct 1153 ms 51112 KB Output is correct
12 Correct 1181 ms 50976 KB Output is correct
13 Correct 844 ms 49588 KB Output is correct
14 Correct 1233 ms 50352 KB Output is correct
15 Correct 978 ms 51248 KB Output is correct
16 Correct 891 ms 51236 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 2 ms 584 KB Output is correct
20 Correct 3 ms 584 KB Output is correct
21 Correct 3 ms 584 KB Output is correct
22 Correct 2 ms 584 KB Output is correct
23 Correct 2 ms 584 KB Output is correct
24 Correct 2 ms 584 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 712 KB Output is correct
27 Correct 18 ms 1096 KB Output is correct
28 Correct 19 ms 1096 KB Output is correct
29 Correct 19 ms 1096 KB Output is correct
30 Correct 18 ms 1096 KB Output is correct
31 Correct 17 ms 1096 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 34 ms 29108 KB Output is correct
34 Correct 60 ms 49680 KB Output is correct
35 Correct 66 ms 50968 KB Output is correct
36 Correct 60 ms 49564 KB Output is correct
37 Correct 56 ms 50316 KB Output is correct
38 Correct 55 ms 51248 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 243 ms 23000 KB Output is correct
5 Correct 964 ms 49584 KB Output is correct
6 Correct 517 ms 8644 KB Output is correct
7 Correct 818 ms 49572 KB Output is correct
8 Correct 507 ms 17456 KB Output is correct
9 Correct 945 ms 49584 KB Output is correct
10 Correct 981 ms 51248 KB Output is correct
11 Correct 1153 ms 51112 KB Output is correct
12 Correct 1181 ms 50976 KB Output is correct
13 Correct 844 ms 49588 KB Output is correct
14 Correct 1233 ms 50352 KB Output is correct
15 Correct 978 ms 51248 KB Output is correct
16 Correct 891 ms 51236 KB Output is correct
17 Correct 1 ms 584 KB Output is correct
18 Correct 1 ms 584 KB Output is correct
19 Correct 2 ms 584 KB Output is correct
20 Correct 3 ms 584 KB Output is correct
21 Correct 3 ms 584 KB Output is correct
22 Correct 2 ms 584 KB Output is correct
23 Correct 2 ms 584 KB Output is correct
24 Correct 2 ms 584 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 712 KB Output is correct
27 Correct 18 ms 1096 KB Output is correct
28 Correct 19 ms 1096 KB Output is correct
29 Correct 19 ms 1096 KB Output is correct
30 Correct 18 ms 1096 KB Output is correct
31 Correct 17 ms 1096 KB Output is correct
32 Correct 1 ms 584 KB Output is correct
33 Correct 34 ms 29108 KB Output is correct
34 Correct 60 ms 49680 KB Output is correct
35 Correct 66 ms 50968 KB Output is correct
36 Correct 60 ms 49564 KB Output is correct
37 Correct 56 ms 50316 KB Output is correct
38 Correct 55 ms 51248 KB Output is correct
39 Correct 0 ms 584 KB Output is correct
40 Correct 1 ms 584 KB Output is correct
41 Correct 1 ms 584 KB Output is correct
42 Correct 249 ms 23092 KB Output is correct
43 Correct 892 ms 49584 KB Output is correct
44 Correct 516 ms 8644 KB Output is correct
45 Correct 926 ms 49584 KB Output is correct
46 Correct 579 ms 17544 KB Output is correct
47 Correct 1010 ms 49584 KB Output is correct
48 Correct 1155 ms 51120 KB Output is correct
49 Correct 1137 ms 51084 KB Output is correct
50 Correct 1074 ms 50988 KB Output is correct
51 Correct 714 ms 49536 KB Output is correct
52 Correct 1145 ms 50312 KB Output is correct
53 Correct 888 ms 51248 KB Output is correct
54 Correct 877 ms 51224 KB Output is correct
55 Correct 1 ms 584 KB Output is correct
56 Correct 121 ms 49588 KB Output is correct
57 Correct 949 ms 49584 KB Output is correct
58 Correct 468 ms 9148 KB Output is correct
59 Correct 878 ms 49536 KB Output is correct
60 Correct 443 ms 18088 KB Output is correct
61 Correct 847 ms 49544 KB Output is correct
62 Correct 949 ms 51248 KB Output is correct
63 Correct 871 ms 50736 KB Output is correct
64 Correct 1086 ms 50588 KB Output is correct
65 Correct 959 ms 49584 KB Output is correct
66 Correct 1133 ms 50312 KB Output is correct
67 Correct 1056 ms 51248 KB Output is correct
68 Correct 987 ms 51196 KB Output is correct
69 Correct 1 ms 584 KB Output is correct
70 Correct 1 ms 584 KB Output is correct
71 Correct 2 ms 584 KB Output is correct
72 Correct 3 ms 584 KB Output is correct
73 Correct 3 ms 584 KB Output is correct
74 Correct 3 ms 584 KB Output is correct
75 Correct 2 ms 584 KB Output is correct
76 Correct 1 ms 584 KB Output is correct
77 Correct 0 ms 584 KB Output is correct
78 Correct 2 ms 584 KB Output is correct
79 Correct 2 ms 584 KB Output is correct
80 Correct 3 ms 584 KB Output is correct
81 Correct 2 ms 584 KB Output is correct
82 Correct 2 ms 584 KB Output is correct
83 Correct 3 ms 584 KB Output is correct
84 Correct 1 ms 584 KB Output is correct
85 Correct 4 ms 584 KB Output is correct
86 Correct 19 ms 1096 KB Output is correct
87 Correct 19 ms 1096 KB Output is correct
88 Correct 23 ms 1096 KB Output is correct
89 Correct 19 ms 1096 KB Output is correct
90 Correct 19 ms 1096 KB Output is correct
91 Correct 1 ms 584 KB Output is correct
92 Correct 1 ms 712 KB Output is correct
93 Correct 13 ms 1096 KB Output is correct
94 Correct 18 ms 1096 KB Output is correct
95 Correct 16 ms 1096 KB Output is correct
96 Correct 15 ms 1096 KB Output is correct
97 Correct 12 ms 1096 KB Output is correct
98 Correct 1 ms 584 KB Output is correct
99 Correct 66 ms 49580 KB Output is correct
100 Correct 65 ms 49660 KB Output is correct
101 Correct 61 ms 50812 KB Output is correct
102 Correct 61 ms 49584 KB Output is correct
103 Correct 62 ms 50428 KB Output is correct
104 Correct 63 ms 51252 KB Output is correct
105 Correct 1 ms 584 KB Output is correct
106 Correct 37 ms 29084 KB Output is correct
107 Correct 63 ms 49560 KB Output is correct
108 Correct 59 ms 50912 KB Output is correct
109 Correct 63 ms 49584 KB Output is correct
110 Correct 59 ms 50332 KB Output is correct
111 Correct 59 ms 51248 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 145 ms 40992 KB Output is correct
4 Correct 1218 ms 51248 KB Output is correct
5 Correct 987 ms 26124 KB Output is correct
6 Correct 1150 ms 51248 KB Output is correct
7 Correct 931 ms 35240 KB Output is correct
8 Correct 1137 ms 51216 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 0 ms 584 KB Output is correct
12 Correct 0 ms 584 KB Output is correct
13 Correct 2 ms 584 KB Output is correct
14 Incorrect 2 ms 584 KB Output isn't correct
15 Halted 0 ms 0 KB -