oj.uz

답안 #972757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972757 2024-05-01T06:16:01 Z dubabuba 밀림 점프 (APIO21_jumps) C++14
60 / 100
 1368 ms 172624 KB 
#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxk = 32;
const int mxn = 2e5 + 10;
const int inf = 1e9 + 10;
int L[mxn], h[mxn];
int R[mxn], n;

vector<int> adj[mxn];
int mx[mxk][mxn], mn[mxk][mxn];
pii ll[mxk][mxn], rr[mxk][mxn];

pii str[mxn * 4];
void build(int id, int tl, int tr) {
	if(tl == tr) {
		str[id] = MP(h[tl], tl);
		return;
	}
	int tm = (tl + tr) / 2;
	build(id * 2 + 1, tl, tm);
	build(id * 2 + 2, tm + 1, tr);
	str[id] = max(str[id * 2 + 1], str[id * 2 + 2]);
}

pii query(int id, int tl, int tr, int l, int r) {
	if(l > r) return MP(0, -1);
	if(tl == l && r == tr) return str[id];
	int tm = (tl + tr) / 2;
	if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
	pii LQ = query(id * 2 + 1, tl, tm, l, tm);
	pii RQ = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
	return max(LQ, RQ);
}

void init(int N, vector<int> H) {
	memset(L, -1, sizeof L);
	memset(R, -1, sizeof R);
	n = N;

	for(int i = 0; i <= N; i++)
	for(int k = 0; k <= mxk; k++) {
		mn[k][i] = mx[k][i] = 0;
		ll[k][i] = rr[k][i] = MP(0, 0);
	}

	stack<int> st;
	for(int i = 1; i < N; i++) {
		while(st.size() && H[st.top()] <= H[i])
			st.pop();
		if(st.size()) L[i] = st.top();
		else L[i] = -1;
		st.push(i);
	}

	stack<int> en;
	for(int i = N - 1; i >= 0; i--) {
		while(en.size() && H[en.top()] <= H[i])
			en.pop();
		if(en.size()) R[i] = en.top();
		else R[i] = -1;
		en.push(i);
	}

	for(int i = 0; i < N; i++) {
		h[i] = H[i];
		if(L[i] > -1) {
			adj[i].push_back(L[i]);
			if(mn[0][H[i]] == 0)
				mn[0][H[i]] = H[L[i]];
			ono_min(mn[0][H[i]], H[L[i]]);
			ono_max(mx[0][H[i]], H[L[i]]);
			ll[0][i] = MP(H[L[i]], L[i]);
		}
		if(R[i] > -1) {
			adj[i].push_back(R[i]);
			if(mn[0][H[i]] == 0)
				mn[0][H[i]] = H[R[i]];
			ono_min(mn[0][H[i]], H[R[i]]);
			ono_max(mx[0][H[i]], H[R[i]]);
			rr[0][i] = MP(H[R[i]], R[i]);
		}
	}

	build(0, 0, n - 1);
	for(int k = 1; k < mxk; k++)
	for(int i = 1; i <= n; i++) {
		int mnj = mn[k - 1][i];
		int mxj = mx[k - 1][i];

		if(mnj) mn[k][i] = mn[k - 1][mnj];
		if(mxj) mx[k][i] = mx[k - 1][mxj];
	}

	for(int k = 1; k < mxk; k++)
	for(int i = 0; i < n; i++) {
		pii pl = ll[k - 1][i];
		pii pr = rr[k - 1][i];

		if(pl.ss) ll[k][i] = ll[k - 1][pl.ss];
		if(pr.ss) rr[k][i] = rr[k - 1][pr.ss];
	}
}

int solve(int s, int f) {
	if(s == f) return 0;
	int ans = 0;
	for(int k = mxk - 1; k >= 0; k--)
	if(mx[k][s] && mx[k][s] <= f) {
		s = mx[k][s];
		ans += (1 << k);
	}

	for(int k = mxk - 1; k >= 0; k--)
	if(mn[k][s] && mn[k][s] <= f) {
		s = mn[k][s];
		ans += (1 << k);
	}
	if(s == f) return ans;
	return inf;
}

int minimum_jumps(int A, int B, int C, int D) {
	pii bet = query(0, 0, n - 1, B + 1, C - 1);
	int bet_mx = bet.ff;
	int bet_id = bet.ss;
	// cout << endl;
	// cout << "min jump: " << A << ' ' << B << ' ' << C << ' ' << D << endl;
	// cout << "mid = " << bet_id << ' ' << bet_mx << endl;

	int l = B;
	for(int i = mxk - 1; i >= 0; i--) {
		pii p = ll[i][l];
		int hi = p.ff;
		int id = p.ss;

		if(hi == 0) continue;
		if(hi > bet_mx) continue;
		if(id < A) continue;
		l = id;
	}

	auto think = [&](int i) -> int {
		if(i == -1) return inf;
		if(i < A) return inf;

		int cur = C, cmp = max(h[i], bet_mx);
		if(cmp < h[C]) return solve(h[i], h[C]);
		for(int k = mxk - 1; k >= 0; k--) {
			pii p = rr[k][cur];
			int hi = p.ff;
			int id = p.ss;

			if(hi == 0) continue;
			if(hi > cmp) continue;
			if(id > D) continue;
			cur = id;
		}

		if(R[cur] == -1) return inf;
		if(R[cur] > D) return inf;
		if(cmp > h[R[cur]]) return inf;
		// cout << " think " << i << ' ' << R[cur] << endl;
		return solve(h[i], h[R[cur]]);
	};

	int AL = think(l);
	int PL = think(L[l]);

	pii GL = query(0, 0, n - 1, A, B);
	int L_mx = GL.ff;
	int L_id = GL.ss;
	int LL = INT_MAX;

	auto go_left = [&](int ML) -> int {
		int ret = 0;

		int L_most = ML;
		for(int k = mxk - 1; k >= 0; k--) {
			pii p = ll[k][L_most];
			int hi = p.ff;
			int id = p.ss;

			if(hi == 0) continue;
			if(hi > bet_mx) continue;
			L_most = id;
			ret += (1 << k);
		}

		if(L[L_most] != -1) {
			L_most = L[L_most];
			ret++;
		}

		int R_most = L_most;
		for(int k = mxk - 1; k >= 0; k--) {
			if(C <= R_most && R_most <= D)
				return ret;
			pii p = rr[k][R_most];
			int hi = p.ff;
			int id = p.ss;

			if(hi == 0) continue;
			if(id > D) continue;
			R_most = id;
			ret += (1 << k);
		}
		return INT_MAX;
	};

	LL = go_left(L_id);

	int L_most = B, sus = 0;
	for(int k = mxk - 1; k >= 0; k--) {
		pii p = ll[k][L_most];
		int hi = p.ff;
		int id = p.ss;

		if(hi == 0) continue;
		if(hi > bet_mx) continue;
		sus += (1 << k);
		L_most = id;
	}

	L_most = L[L_most];
	int gay = inf;
	if(L_most != -1 && L_most < A) {
		int R_most = C;
		for(int k = mxk - 1; k >= 0; k--) {
			pii p = ll[k][R_most];
			int hi = p.ff;
			int id = p.ss;

			if(hi == 0) continue;
			if(hi > h[L_most]) continue;
			if(id > D) continue;
			R_most = id;
		}

		R_most = R[R_most];
		// cout << A << ' ' << B << ' ' << C << ' ' << D << endl;
		// cout << L_most << ' ' << R_most << endl;
		if(R_most != -1 && C <= R_most && R_most <= D)
			gay = solve(h[L_most], h[R_most]) + solve(L_mx, h[L_most]);
	}

	if(min({AL, PL, LL, gay}) != inf) return min({AL, PL, LL, gay});
	return -1;
}
// 7 4 1 2 5 3 6 9 8
// 9 8 7 6 5 4 3 2 1

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:137:6: warning: unused variable 'bet_id' [-Wunused-variable]
  137 |  int bet_id = bet.ss;
      |      ^~~~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:54:23: warning: iteration 32 invokes undefined behavior [-Waggressive-loop-optimizations]
   54 |   mn[k][i] = mx[k][i] = 0;
      |              ~~~~~~~~~^~~
jumps.cpp:53:19: note: within this loop
   53 |  for(int k = 0; k <= mxk; k++) {
      |                 ~~^~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 32600 KB Output is correct
2 Correct 5 ms 32600 KB Output is correct
3 Correct 183 ms 144936 KB Output is correct
4 Correct 1121 ms 172484 KB Output is correct
5 Correct 888 ms 103928 KB Output is correct
6 Correct 1085 ms 172372 KB Output is correct
7 Correct 878 ms 130568 KB Output is correct
8 Correct 1053 ms 172492 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 36696 KB Output is correct
2 Correct 5 ms 32600 KB Output is correct
3 Correct 5 ms 32600 KB Output is correct
4 Correct 6 ms 32600 KB Output is correct
5 Incorrect 6 ms 32600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 36696 KB Output is correct
2 Correct 5 ms 32600 KB Output is correct
3 Correct 5 ms 32600 KB Output is correct
4 Correct 6 ms 32600 KB Output is correct
5 Incorrect 6 ms 32600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 32600 KB Output is correct
2 Correct 5 ms 32600 KB Output is correct
3 Correct 5 ms 32600 KB Output is correct
4 Correct 5 ms 32600 KB Output is correct
5 Correct 106 ms 145452 KB Output is correct
6 Correct 138 ms 171856 KB Output is correct
7 Correct 68 ms 104540 KB Output is correct
8 Correct 138 ms 171484 KB Output is correct
9 Correct 24 ms 54892 KB Output is correct
10 Correct 127 ms 171600 KB Output is correct
11 Correct 114 ms 172508 KB Output is correct
12 Correct 119 ms 171800 KB Output is correct
13 Correct 116 ms 172212 KB Output is correct
14 Correct 125 ms 171464 KB Output is correct
15 Correct 131 ms 171552 KB Output is correct
16 Correct 120 ms 171580 KB Output is correct
17 Correct 121 ms 171460 KB Output is correct
18 Correct 5 ms 36696 KB Output is correct
19 Correct 5 ms 32600 KB Output is correct
20 Correct 5 ms 32600 KB Output is correct
21 Correct 5 ms 32788 KB Output is correct
22 Correct 5 ms 32600 KB Output is correct
23 Correct 6 ms 34648 KB Output is correct
24 Correct 5 ms 32600 KB Output is correct
25 Correct 5 ms 32600 KB Output is correct
26 Correct 5 ms 33112 KB Output is correct
27 Correct 6 ms 33880 KB Output is correct
28 Correct 6 ms 33880 KB Output is correct
29 Correct 6 ms 35928 KB Output is correct
30 Correct 6 ms 33880 KB Output is correct
31 Correct 7 ms 37976 KB Output is correct
32 Correct 5 ms 32504 KB Output is correct
33 Correct 139 ms 171500 KB Output is correct
34 Correct 136 ms 171464 KB Output is correct
35 Correct 115 ms 172496 KB Output is correct
36 Correct 137 ms 171476 KB Output is correct
37 Correct 124 ms 171468 KB Output is correct
38 Correct 120 ms 172216 KB Output is correct
39 Correct 5 ms 30552 KB Output is correct
40 Correct 77 ms 112780 KB Output is correct
41 Correct 130 ms 171480 KB Output is correct
42 Correct 117 ms 172232 KB Output is correct
43 Correct 128 ms 171528 KB Output is correct
44 Correct 122 ms 171608 KB Output is correct
45 Correct 129 ms 172116 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 4 ms 30552 KB Output is correct
3 Correct 4 ms 28504 KB Output is correct
4 Correct 261 ms 95212 KB Output is correct
5 Correct 916 ms 171700 KB Output is correct
6 Correct 552 ms 53848 KB Output is correct
7 Correct 931 ms 171548 KB Output is correct
8 Correct 542 ms 78624 KB Output is correct
9 Correct 994 ms 171588 KB Output is correct
10 Correct 1280 ms 172488 KB Output is correct
11 Correct 1132 ms 172020 KB Output is correct
12 Correct 1241 ms 172244 KB Output is correct
13 Correct 979 ms 171696 KB Output is correct
14 Correct 1267 ms 171688 KB Output is correct
15 Correct 1000 ms 172400 KB Output is correct
16 Correct 932 ms 172244 KB Output is correct
17 Correct 6 ms 34648 KB Output is correct
18 Correct 5 ms 32600 KB Output is correct
19 Correct 5 ms 32600 KB Output is correct
20 Correct 6 ms 32600 KB Output is correct
21 Correct 6 ms 32600 KB Output is correct
22 Correct 6 ms 32600 KB Output is correct
23 Correct 6 ms 32760 KB Output is correct
24 Correct 6 ms 32740 KB Output is correct
25 Correct 5 ms 32600 KB Output is correct
26 Correct 6 ms 37164 KB Output is correct
27 Correct 19 ms 35928 KB Output is correct
28 Correct 19 ms 33880 KB Output is correct
29 Correct 18 ms 35928 KB Output is correct
30 Correct 20 ms 35928 KB Output is correct
31 Correct 20 ms 35928 KB Output is correct
32 Correct 5 ms 32600 KB Output is correct
33 Correct 88 ms 114544 KB Output is correct
34 Correct 130 ms 171612 KB Output is correct
35 Correct 118 ms 172316 KB Output is correct
36 Correct 130 ms 171632 KB Output is correct
37 Correct 151 ms 171472 KB Output is correct
38 Correct 135 ms 172488 KB Output is correct

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 4 ms 30552 KB Output is correct
3 Correct 4 ms 28504 KB Output is correct
4 Correct 261 ms 95212 KB Output is correct
5 Correct 916 ms 171700 KB Output is correct
6 Correct 552 ms 53848 KB Output is correct
7 Correct 931 ms 171548 KB Output is correct
8 Correct 542 ms 78624 KB Output is correct
9 Correct 994 ms 171588 KB Output is correct
10 Correct 1280 ms 172488 KB Output is correct
11 Correct 1132 ms 172020 KB Output is correct
12 Correct 1241 ms 172244 KB Output is correct
13 Correct 979 ms 171696 KB Output is correct
14 Correct 1267 ms 171688 KB Output is correct
15 Correct 1000 ms 172400 KB Output is correct
16 Correct 932 ms 172244 KB Output is correct
17 Correct 6 ms 34648 KB Output is correct
18 Correct 5 ms 32600 KB Output is correct
19 Correct 5 ms 32600 KB Output is correct
20 Correct 6 ms 32600 KB Output is correct
21 Correct 6 ms 32600 KB Output is correct
22 Correct 6 ms 32600 KB Output is correct
23 Correct 6 ms 32760 KB Output is correct
24 Correct 6 ms 32740 KB Output is correct
25 Correct 5 ms 32600 KB Output is correct
26 Correct 6 ms 37164 KB Output is correct
27 Correct 19 ms 35928 KB Output is correct
28 Correct 19 ms 33880 KB Output is correct
29 Correct 18 ms 35928 KB Output is correct
30 Correct 20 ms 35928 KB Output is correct
31 Correct 20 ms 35928 KB Output is correct
32 Correct 5 ms 32600 KB Output is correct
33 Correct 88 ms 114544 KB Output is correct
34 Correct 130 ms 171612 KB Output is correct
35 Correct 118 ms 172316 KB Output is correct
36 Correct 130 ms 171632 KB Output is correct
37 Correct 151 ms 171472 KB Output is correct
38 Correct 135 ms 172488 KB Output is correct
39 Correct 5 ms 26456 KB Output is correct
40 Correct 4 ms 26340 KB Output is correct
41 Correct 4 ms 24408 KB Output is correct
42 Correct 284 ms 93468 KB Output is correct
43 Correct 1006 ms 171644 KB Output is correct
44 Correct 538 ms 55636 KB Output is correct
45 Correct 962 ms 171604 KB Output is correct
46 Correct 548 ms 79656 KB Output is correct
47 Correct 884 ms 171620 KB Output is correct
48 Correct 1243 ms 172624 KB Output is correct
49 Correct 1165 ms 171900 KB Output is correct
50 Correct 1241 ms 172248 KB Output is correct
51 Correct 942 ms 171676 KB Output is correct
52 Correct 1307 ms 171480 KB Output is correct
53 Correct 952 ms 172240 KB Output is correct
54 Correct 986 ms 172440 KB Output is correct
55 Correct 6 ms 38900 KB Output is correct
56 Correct 186 ms 171588 KB Output is correct
57 Correct 993 ms 171460 KB Output is correct
58 Correct 432 ms 55388 KB Output is correct
59 Correct 937 ms 171464 KB Output is correct
60 Correct 373 ms 81232 KB Output is correct
61 Correct 937 ms 171464 KB Output is correct
62 Correct 1276 ms 172284 KB Output is correct
63 Correct 1229 ms 171976 KB Output is correct
64 Correct 1179 ms 171980 KB Output is correct
65 Correct 980 ms 171544 KB Output is correct
66 Correct 1368 ms 171476 KB Output is correct
67 Correct 974 ms 172088 KB Output is correct
68 Correct 922 ms 172240 KB Output is correct
69 Correct 10 ms 85592 KB Output is correct
70 Correct 11 ms 85688 KB Output is correct
71 Correct 12 ms 87640 KB Output is correct
72 Correct 11 ms 85824 KB Output is correct
73 Correct 12 ms 87640 KB Output is correct
74 Correct 11 ms 85848 KB Output is correct
75 Correct 11 ms 87768 KB Output is correct
76 Correct 10 ms 87640 KB Output is correct
77 Correct 10 ms 85592 KB Output is correct
78 Correct 11 ms 85592 KB Output is correct
79 Correct 12 ms 85848 KB Output is correct
80 Correct 11 ms 85848 KB Output is correct
81 Correct 12 ms 87896 KB Output is correct
82 Correct 11 ms 85848 KB Output is correct
83 Correct 12 ms 87640 KB Output is correct
84 Correct 10 ms 87640 KB Output is correct
85 Correct 12 ms 85848 KB Output is correct
86 Correct 24 ms 88408 KB Output is correct
87 Correct 22 ms 86360 KB Output is correct
88 Correct 22 ms 86360 KB Output is correct
89 Correct 24 ms 86588 KB Output is correct
90 Correct 22 ms 86360 KB Output is correct
91 Correct 11 ms 87640 KB Output is correct
92 Correct 11 ms 85848 KB Output is correct
93 Correct 23 ms 88408 KB Output is correct
94 Correct 30 ms 86360 KB Output is correct
95 Correct 22 ms 86360 KB Output is correct
96 Correct 25 ms 86360 KB Output is correct
97 Correct 22 ms 86360 KB Output is correct
98 Correct 10 ms 87640 KB Output is correct
99 Correct 127 ms 171460 KB Output is correct
100 Correct 131 ms 171484 KB Output is correct
101 Correct 122 ms 172180 KB Output is correct
102 Correct 132 ms 171728 KB Output is correct
103 Correct 128 ms 171464 KB Output is correct
104 Correct 114 ms 172160 KB Output is correct
105 Correct 10 ms 83544 KB Output is correct
106 Correct 80 ms 134088 KB Output is correct
107 Correct 131 ms 171604 KB Output is correct
108 Correct 114 ms 172388 KB Output is correct
109 Correct 137 ms 171460 KB Output is correct
110 Correct 128 ms 171460 KB Output is correct
111 Correct 128 ms 172072 KB Output is correct

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 32600 KB Output is correct
2 Correct 5 ms 32600 KB Output is correct
3 Correct 183 ms 144936 KB Output is correct
4 Correct 1121 ms 172484 KB Output is correct
5 Correct 888 ms 103928 KB Output is correct
6 Correct 1085 ms 172372 KB Output is correct
7 Correct 878 ms 130568 KB Output is correct
8 Correct 1053 ms 172492 KB Output is correct
9 Correct 5 ms 36696 KB Output is correct
10 Correct 5 ms 32600 KB Output is correct
11 Correct 5 ms 32600 KB Output is correct
12 Correct 6 ms 32600 KB Output is correct
13 Incorrect 6 ms 32600 KB Output isn't correct
14 Halted 0 ms 0 KB -