oj.uz

Submission #692526

# Submission time Handle Problem Language Result Execution time Memory
692526 2023-02-01T17:53:53 Z gustjwkd1007 Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 1750 ms 74712 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}

int inv[210000], dep[210000];
int sparse[2][210000][30];
vector <int> input, gan[210000];
int max_seg[810000];
int n;

int build(int s, int e, int ind){
	if(s==e)
		return max_seg[ind] = input[s];
	int m = (s+e)/2;
	return max_seg[ind] = max(build(s, m, ind*2), build(m+1, e, ind*2+1));
}

int rmq(int s, int e, int ind, int x, int y){
	if(s>y||e<x)
		return 0;
	if(s>=x&&e<=y)
		return max_seg[ind];
	return max(
		rmq(s, (s+e)/2, ind*2, x, y),
		rmq((s+e)/2+1, e, ind*2+1, x, y)
	);
}

int low_cd(int C, int D, int M){
	int l = C, r = D;
	while(l<=r){
		int m = (l+r)/2;
		if(rmq(1, n, 1, C, m)>M)
			r = m-1;
		else
			l = m+1;
	}
	return l;
}

int low_ab(int A, int B, int M){
	int l = A, r = B;
	while(l<=r){
		int m = (l+r)/2;
		if(rmq(1, n, 1, m, B)<M)
			r = m-1;
		else
			l = m+1;
	}
	return l-1;
}

int dist(int s, int e){
	int re=0;
	for(int i=29;i>=0;i--)if(dep[sparse[1][s][i]]>=dep[e]){
		re += (1 << i);
		s = sparse[1][s][i];
	}
	return re - dep[e] + dep[s];
}

void set_inv(){
	for(int i=1;i<=n;i++)
		inv[input[i]]=i;
}

void dfs(int now){
	for(int t=0;t<2;t++){
		for(int i=1;i<30;i++)
			sparse[t][now][i] = sparse[t][sparse[t][now][i-1]][i-1];
	}
	for(int nex : gan[now]){
		dep[nex] = dep[now]+1;
		dfs(nex);
	}
}

void set_sparse(){
	stack <int> ms;
	ms.push(0);
	for(int i=1;i<=n;i++){
		for(;input[ms.top()]<input[i];ms.pop());
		sparse[0][i][0] = ms.top();
		ms.push(i);
	}

	while(ms.size()) ms.pop();

	ms.push(0);
	for(int i=n;i>0;i--){
		for(;input[ms.top()]<input[i];ms.pop());
		sparse[1][i][0] = ms.top();
		ms.push(i);
	}

	for(int i=1;i<=n;i++)if(input[sparse[0][i][0]]>input[sparse[1][i][0]])
		swap(sparse[0][i][0], sparse[1][i][0]);
	for(int i=1;i<=n;i++)
		gan[sparse[0][i][0]].push_back(i);

	dfs(0);
}

void init(int N, std::vector<int> H) {
	input.push_back(INF);
	input.insert(input.end(), H.begin(), H.end());
	n=N;
	set_inv();
	set_sparse();
	build(1, n, 1);
}

int minimum_jumps(int A, int B, int C, int D) {
	A++, B++, C++, D++;
	int M = rmq(1, n, 1, B+1, C-1);
	int la = low_ab(A, B, M);
	int lc = low_cd(C, D, M);
	if(lc>D)
		return -1;
	if(la<A)
		return dist(inv[rmq(1, n, 1, A, B)], lc);
	if(rmq(1, n, 1, C, D)>input[la])
		return 1;
	if(la==B)
		return -1;
	return dist(inv[rmq(1, n, 1, la+1, B)], lc);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 272 ms 60900 KB Output is correct
4 Correct 1699 ms 74632 KB Output is correct
5 Correct 1322 ms 40104 KB Output is correct
6 Correct 1686 ms 74616 KB Output is correct
7 Correct 1152 ms 53204 KB Output is correct
8 Correct 1750 ms 74712 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 3 ms 5200 KB Output is correct
5 Correct 5 ms 5200 KB Output is correct
6 Correct 4 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 5 ms 5200 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 5 ms 5200 KB Output is correct
11 Correct 5 ms 5328 KB Output is correct
12 Correct 5 ms 5328 KB Output is correct
13 Incorrect 8 ms 5200 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 3 ms 5200 KB Output is correct
5 Correct 5 ms 5200 KB Output is correct
6 Correct 4 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 5 ms 5200 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 5 ms 5200 KB Output is correct
11 Correct 5 ms 5328 KB Output is correct
12 Correct 5 ms 5328 KB Output is correct
13 Incorrect 8 ms 5200 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 3 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 2 ms 5200 KB Output is correct
5 Correct 109 ms 51496 KB Output is correct
6 Correct 115 ms 62396 KB Output is correct
7 Correct 66 ms 34444 KB Output is correct
8 Correct 109 ms 62364 KB Output is correct
9 Correct 26 ms 13800 KB Output is correct
10 Correct 119 ms 62328 KB Output is correct
11 Correct 107 ms 74608 KB Output is correct
12 Correct 103 ms 71572 KB Output is correct
13 Incorrect 104 ms 71600 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 4 ms 5200 KB Output is correct
2 Correct 3 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 325 ms 31348 KB Output is correct
5 Correct 1139 ms 62256 KB Output is correct
6 Correct 675 ms 14752 KB Output is correct
7 Correct 1134 ms 62320 KB Output is correct
8 Correct 613 ms 25228 KB Output is correct
9 Correct 1092 ms 62328 KB Output is correct
10 Correct 1203 ms 74636 KB Output is correct
11 Correct 1142 ms 73180 KB Output is correct
12 Correct 1167 ms 73332 KB Output is correct
13 Correct 1128 ms 62568 KB Output is correct
14 Correct 1101 ms 73888 KB Output is correct
15 Correct 869 ms 73780 KB Output is correct
16 Correct 1048 ms 73828 KB Output is correct
17 Correct 4 ms 5200 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 4 ms 5200 KB Output is correct
20 Correct 5 ms 5328 KB Output is correct
21 Correct 4 ms 5328 KB Output is correct
22 Correct 5 ms 5200 KB Output is correct
23 Correct 5 ms 5328 KB Output is correct
24 Correct 5 ms 5328 KB Output is correct
25 Correct 3 ms 5200 KB Output is correct
26 Correct 5 ms 5456 KB Output is correct
27 Correct 23 ms 5712 KB Output is correct
28 Correct 25 ms 5840 KB Output is correct
29 Correct 22 ms 5820 KB Output is correct
30 Correct 20 ms 5840 KB Output is correct
31 Correct 11 ms 5840 KB Output is correct
32 Correct 3 ms 5200 KB Output is correct
33 Correct 63 ms 38128 KB Output is correct
34 Correct 116 ms 62340 KB Output is correct
35 Correct 105 ms 73092 KB Output is correct
36 Correct 111 ms 62432 KB Output is correct
37 Correct 183 ms 73812 KB Output is correct
38 Correct 103 ms 73840 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 3 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 325 ms 31348 KB Output is correct
5 Correct 1139 ms 62256 KB Output is correct
6 Correct 675 ms 14752 KB Output is correct
7 Correct 1134 ms 62320 KB Output is correct
8 Correct 613 ms 25228 KB Output is correct
9 Correct 1092 ms 62328 KB Output is correct
10 Correct 1203 ms 74636 KB Output is correct
11 Correct 1142 ms 73180 KB Output is correct
12 Correct 1167 ms 73332 KB Output is correct
13 Correct 1128 ms 62568 KB Output is correct
14 Correct 1101 ms 73888 KB Output is correct
15 Correct 869 ms 73780 KB Output is correct
16 Correct 1048 ms 73828 KB Output is correct
17 Correct 4 ms 5200 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 4 ms 5200 KB Output is correct
20 Correct 5 ms 5328 KB Output is correct
21 Correct 4 ms 5328 KB Output is correct
22 Correct 5 ms 5200 KB Output is correct
23 Correct 5 ms 5328 KB Output is correct
24 Correct 5 ms 5328 KB Output is correct
25 Correct 3 ms 5200 KB Output is correct
26 Correct 5 ms 5456 KB Output is correct
27 Correct 23 ms 5712 KB Output is correct
28 Correct 25 ms 5840 KB Output is correct
29 Correct 22 ms 5820 KB Output is correct
30 Correct 20 ms 5840 KB Output is correct
31 Correct 11 ms 5840 KB Output is correct
32 Correct 3 ms 5200 KB Output is correct
33 Correct 63 ms 38128 KB Output is correct
34 Correct 116 ms 62340 KB Output is correct
35 Correct 105 ms 73092 KB Output is correct
36 Correct 111 ms 62432 KB Output is correct
37 Correct 183 ms 73812 KB Output is correct
38 Correct 103 ms 73840 KB Output is correct
39 Correct 3 ms 5200 KB Output is correct
40 Correct 3 ms 5200 KB Output is correct
41 Correct 3 ms 5200 KB Output is correct
42 Correct 245 ms 31380 KB Output is correct
43 Correct 940 ms 62268 KB Output is correct
44 Correct 588 ms 14788 KB Output is correct
45 Correct 1031 ms 62248 KB Output is correct
46 Correct 499 ms 25160 KB Output is correct
47 Correct 898 ms 62356 KB Output is correct
48 Correct 1034 ms 74568 KB Output is correct
49 Correct 980 ms 73208 KB Output is correct
50 Correct 1014 ms 73160 KB Output is correct
51 Correct 862 ms 62436 KB Output is correct
52 Correct 1200 ms 73808 KB Output is correct
53 Correct 901 ms 73844 KB Output is correct
54 Correct 792 ms 73800 KB Output is correct
55 Correct 3 ms 5200 KB Output is correct
56 Correct 177 ms 62172 KB Output is correct
57 Correct 1451 ms 62340 KB Output is correct
58 Correct 622 ms 15396 KB Output is correct
59 Correct 1375 ms 62280 KB Output is correct
60 Correct 500 ms 25800 KB Output is correct
61 Correct 1297 ms 62324 KB Output is correct
62 Correct 1533 ms 74568 KB Output is correct
63 Correct 1469 ms 71796 KB Output is correct
64 Correct 1610 ms 70728 KB Output is correct
65 Correct 1515 ms 62440 KB Output is correct
66 Correct 1581 ms 73736 KB Output is correct
67 Correct 1332 ms 73800 KB Output is correct
68 Correct 1219 ms 73752 KB Output is correct
69 Correct 3 ms 5200 KB Output is correct
70 Correct 3 ms 5200 KB Output is correct
71 Correct 4 ms 5200 KB Output is correct
72 Correct 5 ms 5200 KB Output is correct
73 Correct 6 ms 5200 KB Output is correct
74 Correct 5 ms 5328 KB Output is correct
75 Correct 5 ms 5328 KB Output is correct
76 Correct 2 ms 5200 KB Output is correct
77 Correct 3 ms 5200 KB Output is correct
78 Correct 4 ms 5200 KB Output is correct
79 Correct 5 ms 5200 KB Output is correct
80 Correct 6 ms 5200 KB Output is correct
81 Correct 5 ms 5200 KB Output is correct
82 Correct 5 ms 5328 KB Output is correct
83 Correct 5 ms 5200 KB Output is correct
84 Correct 3 ms 5200 KB Output is correct
85 Correct 4 ms 5328 KB Output is correct
86 Correct 22 ms 5712 KB Output is correct
87 Correct 24 ms 5840 KB Output is correct
88 Correct 22 ms 5768 KB Output is correct
89 Correct 23 ms 5904 KB Output is correct
90 Correct 21 ms 5840 KB Output is correct
91 Correct 3 ms 5328 KB Output is correct
92 Correct 3 ms 5456 KB Output is correct
93 Correct 23 ms 5712 KB Output is correct
94 Correct 22 ms 5840 KB Output is correct
95 Correct 20 ms 5712 KB Output is correct
96 Correct 35 ms 5840 KB Output is correct
97 Correct 18 ms 5840 KB Output is correct
98 Correct 3 ms 5200 KB Output is correct
99 Correct 118 ms 62196 KB Output is correct
100 Correct 108 ms 62344 KB Output is correct
101 Correct 119 ms 72196 KB Output is correct
102 Correct 122 ms 62476 KB Output is correct
103 Correct 195 ms 73936 KB Output is correct
104 Correct 100 ms 73844 KB Output is correct
105 Correct 3 ms 5200 KB Output is correct
106 Correct 63 ms 38056 KB Output is correct
107 Correct 108 ms 62320 KB Output is correct
108 Correct 120 ms 73080 KB Output is correct
109 Correct 113 ms 62468 KB Output is correct
110 Correct 174 ms 73840 KB Output is correct
111 Correct 105 ms 73836 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 272 ms 60900 KB Output is correct
4 Correct 1699 ms 74632 KB Output is correct
5 Correct 1322 ms 40104 KB Output is correct
6 Correct 1686 ms 74616 KB Output is correct
7 Correct 1152 ms 53204 KB Output is correct
8 Correct 1750 ms 74712 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 3 ms 5200 KB Output is correct
13 Correct 5 ms 5200 KB Output is correct
14 Correct 4 ms 5200 KB Output is correct
15 Correct 4 ms 5200 KB Output is correct
16 Correct 5 ms 5200 KB Output is correct
17 Correct 3 ms 5200 KB Output is correct
18 Correct 5 ms 5200 KB Output is correct
19 Correct 5 ms 5328 KB Output is correct
20 Correct 5 ms 5328 KB Output is correct
21 Incorrect 8 ms 5200 KB Output isn't correct
22 Halted 0 ms 0 KB -