oj.uz

답안 #972552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972552 2024-04-30T14:40:46 Z dubabuba 밀림 점프 (APIO21_jumps) C++14
48 / 100
 921 ms 104576 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;
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;

	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];
	}

	// for(int i = 0; i < n; i++)
	// 	cout << R[i] << ' ';
	// cout << endl;
}

int solve(int s, int f) {
	int ans = 0;
	// cout << "solve: " << s << ' ' << f << endl;
	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 INT_MAX;
}

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 INT_MAX;
		if(i < A) return INT_MAX;

		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(p == MP(0, 0)) continue;
			if(hi > cmp) continue;
			if(id > D) continue;
			// cout << "..." << cur << ' ' << k << endl;
			cur = id;
		}

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

	// cout << l << endl;
	int AL = think(l);
	int PL = think(L[l]);
	// cout << AL << ' ' << PL << endl;
	if(min(AL, PL) != INT_MAX) return min(AL, PL);
	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:138:6: warning: unused variable 'bet_id' [-Wunused-variable]
  138 |  int bet_id = bet.ss;
      |      ^~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 13656 KB Output is correct
2 Correct 2 ms 13656 KB Output is correct
3 Correct 129 ms 78160 KB Output is correct
4 Correct 814 ms 82904 KB Output is correct
5 Correct 712 ms 73112 KB Output is correct
6 Correct 896 ms 82744 KB Output is correct
7 Correct 575 ms 76516 KB Output is correct
8 Correct 812 ms 82800 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19800 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 53 ms 53072 KB Output is correct
6 Correct 61 ms 55360 KB Output is correct
7 Correct 33 ms 48228 KB Output is correct
8 Correct 61 ms 55508 KB Output is correct
9 Correct 13 ms 40024 KB Output is correct
10 Correct 64 ms 55552 KB Output is correct
11 Correct 50 ms 82988 KB Output is correct
12 Correct 54 ms 86492 KB Output is correct
13 Incorrect 52 ms 86712 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 13656 KB Output is correct
2 Correct 2 ms 7496 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 177 ms 47644 KB Output is correct
5 Correct 732 ms 55500 KB Output is correct
6 Correct 459 ms 40276 KB Output is correct
7 Correct 751 ms 55496 KB Output is correct
8 Correct 408 ms 46276 KB Output is correct
9 Correct 736 ms 55628 KB Output is correct
10 Correct 829 ms 82892 KB Output is correct
11 Correct 800 ms 86220 KB Output is correct
12 Correct 845 ms 86732 KB Output is correct
13 Correct 759 ms 55516 KB Output is correct
14 Correct 921 ms 104412 KB Output is correct
15 Correct 697 ms 86744 KB Output is correct
16 Correct 703 ms 87004 KB Output is correct
17 Correct 3 ms 15956 KB Output is correct
18 Correct 3 ms 13656 KB Output is correct
19 Correct 4 ms 17752 KB Output is correct
20 Correct 6 ms 32088 KB Output is correct
21 Correct 8 ms 40304 KB Output is correct
22 Correct 5 ms 30040 KB Output is correct
23 Correct 7 ms 44376 KB Output is correct
24 Correct 6 ms 38232 KB Output is correct
25 Correct 5 ms 32092 KB Output is correct
26 Correct 5 ms 32084 KB Output is correct
27 Correct 14 ms 32344 KB Output is correct
28 Correct 16 ms 48728 KB Output is correct
29 Correct 15 ms 32344 KB Output is correct
30 Correct 18 ms 58968 KB Output is correct
31 Correct 15 ms 46680 KB Output is correct
32 Correct 3 ms 13656 KB Output is correct
33 Correct 36 ms 48156 KB Output is correct
34 Correct 61 ms 55492 KB Output is correct
35 Correct 55 ms 86752 KB Output is correct
36 Correct 60 ms 55500 KB Output is correct
37 Correct 65 ms 104408 KB Output is correct
38 Correct 54 ms 86588 KB Output is correct

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 13656 KB Output is correct
2 Correct 2 ms 7496 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 177 ms 47644 KB Output is correct
5 Correct 732 ms 55500 KB Output is correct
6 Correct 459 ms 40276 KB Output is correct
7 Correct 751 ms 55496 KB Output is correct
8 Correct 408 ms 46276 KB Output is correct
9 Correct 736 ms 55628 KB Output is correct
10 Correct 829 ms 82892 KB Output is correct
11 Correct 800 ms 86220 KB Output is correct
12 Correct 845 ms 86732 KB Output is correct
13 Correct 759 ms 55516 KB Output is correct
14 Correct 921 ms 104412 KB Output is correct
15 Correct 697 ms 86744 KB Output is correct
16 Correct 703 ms 87004 KB Output is correct
17 Correct 3 ms 15956 KB Output is correct
18 Correct 3 ms 13656 KB Output is correct
19 Correct 4 ms 17752 KB Output is correct
20 Correct 6 ms 32088 KB Output is correct
21 Correct 8 ms 40304 KB Output is correct
22 Correct 5 ms 30040 KB Output is correct
23 Correct 7 ms 44376 KB Output is correct
24 Correct 6 ms 38232 KB Output is correct
25 Correct 5 ms 32092 KB Output is correct
26 Correct 5 ms 32084 KB Output is correct
27 Correct 14 ms 32344 KB Output is correct
28 Correct 16 ms 48728 KB Output is correct
29 Correct 15 ms 32344 KB Output is correct
30 Correct 18 ms 58968 KB Output is correct
31 Correct 15 ms 46680 KB Output is correct
32 Correct 3 ms 13656 KB Output is correct
33 Correct 36 ms 48156 KB Output is correct
34 Correct 61 ms 55492 KB Output is correct
35 Correct 55 ms 86752 KB Output is correct
36 Correct 60 ms 55500 KB Output is correct
37 Correct 65 ms 104408 KB Output is correct
38 Correct 54 ms 86588 KB Output is correct
39 Correct 3 ms 13656 KB Output is correct
40 Correct 2 ms 7512 KB Output is correct
41 Correct 2 ms 7512 KB Output is correct
42 Correct 188 ms 47668 KB Output is correct
43 Correct 730 ms 55516 KB Output is correct
44 Correct 491 ms 40280 KB Output is correct
45 Correct 738 ms 55504 KB Output is correct
46 Correct 417 ms 46304 KB Output is correct
47 Correct 795 ms 55500 KB Output is correct
48 Correct 821 ms 82892 KB Output is correct
49 Correct 872 ms 86236 KB Output is correct
50 Correct 869 ms 87004 KB Output is correct
51 Correct 733 ms 55492 KB Output is correct
52 Correct 856 ms 104392 KB Output is correct
53 Correct 768 ms 86864 KB Output is correct
54 Correct 708 ms 87000 KB Output is correct
55 Correct 2 ms 7512 KB Output is correct
56 Correct 98 ms 55256 KB Output is correct
57 Correct 767 ms 55376 KB Output is correct
58 Correct 326 ms 40284 KB Output is correct
59 Correct 765 ms 55512 KB Output is correct
60 Correct 296 ms 44424 KB Output is correct
61 Correct 700 ms 55532 KB Output is correct
62 Correct 800 ms 82904 KB Output is correct
63 Correct 840 ms 86488 KB Output is correct
64 Correct 905 ms 86520 KB Output is correct
65 Correct 723 ms 56040 KB Output is correct
66 Correct 879 ms 104520 KB Output is correct
67 Correct 783 ms 84420 KB Output is correct
68 Correct 706 ms 86984 KB Output is correct
69 Correct 2 ms 13656 KB Output is correct
70 Correct 4 ms 27992 KB Output is correct
71 Correct 5 ms 32088 KB Output is correct
72 Correct 6 ms 40280 KB Output is correct
73 Correct 5 ms 30040 KB Output is correct
74 Correct 7 ms 44376 KB Output is correct
75 Correct 6 ms 36228 KB Output is correct
76 Correct 3 ms 15704 KB Output is correct
77 Correct 2 ms 13656 KB Output is correct
78 Correct 3 ms 17752 KB Output is correct
79 Correct 5 ms 32088 KB Output is correct
80 Correct 7 ms 40280 KB Output is correct
81 Correct 6 ms 30040 KB Output is correct
82 Correct 7 ms 44376 KB Output is correct
83 Correct 6 ms 38232 KB Output is correct
84 Correct 5 ms 32096 KB Output is correct
85 Correct 7 ms 32088 KB Output is correct
86 Correct 16 ms 32344 KB Output is correct
87 Correct 17 ms 48984 KB Output is correct
88 Correct 14 ms 32344 KB Output is correct
89 Correct 20 ms 58968 KB Output is correct
90 Correct 15 ms 46680 KB Output is correct
91 Correct 5 ms 32088 KB Output is correct
92 Correct 5 ms 32088 KB Output is correct
93 Correct 14 ms 32344 KB Output is correct
94 Correct 16 ms 48728 KB Output is correct
95 Correct 14 ms 32396 KB Output is correct
96 Correct 19 ms 58968 KB Output is correct
97 Correct 15 ms 46680 KB Output is correct
98 Correct 2 ms 13656 KB Output is correct
99 Correct 61 ms 55492 KB Output is correct
100 Correct 62 ms 55512 KB Output is correct
101 Correct 52 ms 86732 KB Output is correct
102 Correct 63 ms 55524 KB Output is correct
103 Correct 66 ms 104348 KB Output is correct
104 Correct 64 ms 86728 KB Output is correct
105 Correct 2 ms 13908 KB Output is correct
106 Correct 36 ms 48208 KB Output is correct
107 Correct 60 ms 55348 KB Output is correct
108 Correct 52 ms 86736 KB Output is correct
109 Correct 61 ms 55516 KB Output is correct
110 Correct 62 ms 104576 KB Output is correct
111 Correct 54 ms 87260 KB Output is correct

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 13656 KB Output is correct
2 Correct 2 ms 13656 KB Output is correct
3 Correct 129 ms 78160 KB Output is correct
4 Correct 814 ms 82904 KB Output is correct
5 Correct 712 ms 73112 KB Output is correct
6 Correct 896 ms 82744 KB Output is correct
7 Correct 575 ms 76516 KB Output is correct
8 Correct 812 ms 82800 KB Output is correct
9 Correct 3 ms 19800 KB Output is correct
10 Correct 3 ms 13796 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct
13 Incorrect 4 ms 19800 KB Output isn't correct
14 Halted 0 ms 0 KB -