oj.uz

답안 #973742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973742 2024-05-02T10:29:47 Z dubabuba 밀림 점프 (APIO21_jumps) C++14
27 / 100
 1423 ms 172816 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(inf, -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 = 0; 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 go_L(int i) { if(i < 0) return -1; return L[i]; }
int go_R(int i) { if(i < 0) return -1; return R[i]; }
int GIS(int l, int r, int upper, bool rev) {
	// if(rev)
	// 	cout << "find " << l << ' ' << r << ": " << upper << endl;
	if(r < l) return -1;
	int cur = (rev) ? r : l;

	for(int k = mxk - 1; k >= 0; k--) {
		pii p = (rev) ? ll[k][cur] : rr[k][cur];
		int hi = p.ff;
		int id = p.ss;

		if(hi == 0) continue;
		if(hi > upper) continue;
		if(id < l || r < id) continue;
		// if(rev) cout << cur << ' ';
		cur = id;
	}
	// if(rev)
	// 	cout << cur << endl;
	if(h[cur] > upper) return cur;
	return (rev) ? cur : go_R(cur);
}


int minimum_jumps(int A, int B, int C, int D) {
	pii PM = query(0, 0, n - 1, B + 1, C - 1);
	pii PL = query(0, 0, n - 1, A, B);
	pii PR = query(0, 0, n - 1, C, D);
	if(PM.ss >= 0 && PM.ff > PR.ff) return -1;

	auto think = [&](int st, int en, bool ML, bool MR) -> int {
		if(st == -1 || en == -1) return inf;
		if(ML) if(st < A || B < st) return inf;
		if(MR) if(en < C || D < en) return inf;
		if(st == en) return 0;
		return solve(h[st], h[en]);
	};

	// cout << endl;
	// cout << A << ' ' << B << " -> " << C << ' ' << D << endl;
	int gay = (PM.ff == inf) ? 0 : PM.ff;

	auto find_en = [&](int st) -> int {
		if(st == -1) return -1;
		int en = GIS(C, D, max(gay, h[st]), 0);
		return en;
	};

	int st1 = GIS(A, B, PM.ff, 1);
	int st2 = go_R(st1);
	int st3 = B;
	int st4 = PL.ss;

	int en1 = find_en(st1);
	int en2 = find_en(st2);
	int en3 = find_en(st3);
	int en4 = find_en(st4);

	int ans1 = think(st1, en1, 1, 1);
	int ans2 = think(st2, en2, 1, 1);
	int ans3 = think(st3, en3, 1, 1);
	int ans4 = think(st4, en4, 1, 1);

	// cout << st1 << ' ' << en1 << " = " << ans1 << endl;
	// cout << st2 << ' ' << en2 << " = " << ans2 << endl;
	// cout << st3 << ' ' << en3 << " = " << ans3 << endl;
	// cout << st4 << ' ' << en4 << " = " << ans4 << endl;

	int sda = inf;
	if(PM.ff > PL.ff) {
		int st = PL.ss;
		int mid = GIS(0, A - 1, PM.ff, 1);
		int en = (mid > -1) ? GIS(C, D, h[mid], 0) : -1;

		sda = think(st, mid, 1, 0) + think(mid, en, 0, 1);
		// cout << st << ' ' << mid << ' ' << en << " = " << sda << endl;
	}

	int ans = inf;
	ono_min(ans, ans1);
	ono_min(ans, ans2);
	ono_min(ans, ans3);
	ono_min(ans, ans4);
	ono_min(ans, sda);

	return (ans < inf) ? ans : -1;	
}
// 7 4 1 2 5 3 6 9 8
// 9 8 7 6 5 4 3 2 1

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 159056 KB Output is correct
2 Correct 19 ms 159064 KB Output is correct
3 Correct 218 ms 170768 KB Output is correct
4 Correct 1363 ms 172536 KB Output is correct
5 Correct 1125 ms 165916 KB Output is correct
6 Correct 1363 ms 172496 KB Output is correct
7 Correct 1035 ms 169476 KB Output is correct
8 Correct 1423 ms 172816 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 159076 KB Output is correct
2 Correct 19 ms 159132 KB Output is correct
3 Correct 18 ms 159064 KB Output is correct
4 Correct 17 ms 159064 KB Output is correct
5 Correct 19 ms 159064 KB Output is correct
6 Incorrect 18 ms 159064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 159076 KB Output is correct
2 Correct 19 ms 159132 KB Output is correct
3 Correct 18 ms 159064 KB Output is correct
4 Correct 17 ms 159064 KB Output is correct
5 Correct 19 ms 159064 KB Output is correct
6 Incorrect 18 ms 159064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 159064 KB Output is correct
2 Correct 18 ms 159204 KB Output is correct
3 Correct 18 ms 159064 KB Output is correct
4 Correct 18 ms 159064 KB Output is correct
5 Correct 87 ms 170048 KB Output is correct
6 Correct 111 ms 171788 KB Output is correct
7 Correct 70 ms 165468 KB Output is correct
8 Correct 106 ms 171740 KB Output is correct
9 Correct 31 ms 162384 KB Output is correct
10 Correct 111 ms 171792 KB Output is correct
11 Correct 94 ms 172744 KB Output is correct
12 Correct 94 ms 171976 KB Output is correct
13 Incorrect 102 ms 172416 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 159064 KB Output is correct
2 Correct 17 ms 159064 KB Output is correct
3 Correct 17 ms 159092 KB Output is correct
4 Correct 189 ms 165016 KB Output is correct
5 Correct 745 ms 171844 KB Output is correct
6 Correct 483 ms 162640 KB Output is correct
7 Correct 736 ms 171716 KB Output is correct
8 Correct 415 ms 164036 KB Output is correct
9 Correct 757 ms 171792 KB Output is correct
10 Correct 1274 ms 172552 KB Output is correct
11 Correct 1194 ms 171884 KB Output is correct
12 Correct 1161 ms 172368 KB Output is correct
13 Correct 753 ms 171788 KB Output is correct
14 Correct 1210 ms 171792 KB Output is correct
15 Correct 724 ms 172504 KB Output is correct
16 Correct 727 ms 172512 KB Output is correct
17 Correct 18 ms 159064 KB Output is correct
18 Correct 18 ms 159064 KB Output is correct
19 Correct 20 ms 159228 KB Output is correct
20 Correct 19 ms 159064 KB Output is correct
21 Correct 19 ms 159204 KB Output is correct
22 Correct 19 ms 159064 KB Output is correct
23 Correct 19 ms 159064 KB Output is correct
24 Correct 19 ms 159064 KB Output is correct
25 Correct 19 ms 159064 KB Output is correct
26 Correct 18 ms 159064 KB Output is correct
27 Correct 28 ms 159320 KB Output is correct
28 Correct 33 ms 159320 KB Output is correct
29 Correct 35 ms 159320 KB Output is correct
30 Correct 32 ms 159320 KB Output is correct
31 Correct 30 ms 159320 KB Output is correct
32 Correct 18 ms 159064 KB Output is correct
33 Correct 68 ms 165968 KB Output is correct
34 Correct 118 ms 171728 KB Output is correct
35 Correct 96 ms 172748 KB Output is correct
36 Correct 105 ms 171796 KB Output is correct
37 Correct 106 ms 171880 KB Output is correct
38 Correct 97 ms 172248 KB Output is correct

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 159064 KB Output is correct
2 Correct 17 ms 159064 KB Output is correct
3 Correct 17 ms 159092 KB Output is correct
4 Correct 189 ms 165016 KB Output is correct
5 Correct 745 ms 171844 KB Output is correct
6 Correct 483 ms 162640 KB Output is correct
7 Correct 736 ms 171716 KB Output is correct
8 Correct 415 ms 164036 KB Output is correct
9 Correct 757 ms 171792 KB Output is correct
10 Correct 1274 ms 172552 KB Output is correct
11 Correct 1194 ms 171884 KB Output is correct
12 Correct 1161 ms 172368 KB Output is correct
13 Correct 753 ms 171788 KB Output is correct
14 Correct 1210 ms 171792 KB Output is correct
15 Correct 724 ms 172504 KB Output is correct
16 Correct 727 ms 172512 KB Output is correct
17 Correct 18 ms 159064 KB Output is correct
18 Correct 18 ms 159064 KB Output is correct
19 Correct 20 ms 159228 KB Output is correct
20 Correct 19 ms 159064 KB Output is correct
21 Correct 19 ms 159204 KB Output is correct
22 Correct 19 ms 159064 KB Output is correct
23 Correct 19 ms 159064 KB Output is correct
24 Correct 19 ms 159064 KB Output is correct
25 Correct 19 ms 159064 KB Output is correct
26 Correct 18 ms 159064 KB Output is correct
27 Correct 28 ms 159320 KB Output is correct
28 Correct 33 ms 159320 KB Output is correct
29 Correct 35 ms 159320 KB Output is correct
30 Correct 32 ms 159320 KB Output is correct
31 Correct 30 ms 159320 KB Output is correct
32 Correct 18 ms 159064 KB Output is correct
33 Correct 68 ms 165968 KB Output is correct
34 Correct 118 ms 171728 KB Output is correct
35 Correct 96 ms 172748 KB Output is correct
36 Correct 105 ms 171796 KB Output is correct
37 Correct 106 ms 171880 KB Output is correct
38 Correct 97 ms 172248 KB Output is correct
39 Correct 18 ms 159208 KB Output is correct
40 Correct 19 ms 159176 KB Output is correct
41 Correct 19 ms 159056 KB Output is correct
42 Correct 200 ms 165104 KB Output is correct
43 Correct 734 ms 171720 KB Output is correct
44 Correct 460 ms 162568 KB Output is correct
45 Correct 725 ms 171736 KB Output is correct
46 Correct 447 ms 164056 KB Output is correct
47 Correct 714 ms 171732 KB Output is correct
48 Correct 1168 ms 172500 KB Output is correct
49 Correct 1153 ms 171984 KB Output is correct
50 Correct 1100 ms 172500 KB Output is correct
51 Correct 766 ms 171840 KB Output is correct
52 Correct 1150 ms 171792 KB Output is correct
53 Correct 778 ms 172492 KB Output is correct
54 Correct 737 ms 172612 KB Output is correct
55 Correct 17 ms 159064 KB Output is correct
56 Correct 156 ms 171976 KB Output is correct
57 Incorrect 768 ms 171732 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 159056 KB Output is correct
2 Correct 19 ms 159064 KB Output is correct
3 Correct 218 ms 170768 KB Output is correct
4 Correct 1363 ms 172536 KB Output is correct
5 Correct 1125 ms 165916 KB Output is correct
6 Correct 1363 ms 172496 KB Output is correct
7 Correct 1035 ms 169476 KB Output is correct
8 Correct 1423 ms 172816 KB Output is correct
9 Correct 17 ms 159076 KB Output is correct
10 Correct 19 ms 159132 KB Output is correct
11 Correct 18 ms 159064 KB Output is correct
12 Correct 17 ms 159064 KB Output is correct
13 Correct 19 ms 159064 KB Output is correct
14 Incorrect 18 ms 159064 KB Output isn't correct
15 Halted 0 ms 0 KB -