제출 #787014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787014		ToniB	밀림 점프 (APIO21_jumps)	C++17	100 / 100	1227 ms	64736 KiB

jumps

#include <bits/stdc++.h>
#include "jumps.h"
#define X first
#define Y second
using namespace std;
const int MAXN = 2e5 + 2;
const int LOG = 18;
const int OFF = 1 << LOG + 1;

int n, nxt[MAXN][LOG], prv[MAXN], prv_max[MAXN][LOG];
int jump[MAXN][LOG], max_reachable[MAXN][LOG];
pair<int, int> tour[OFF];
vector<int> h;

pair<int, int> f(int x, int l, int r, int ql, int qr){
	if(ql > r || l > qr) return {-1, -1};
	if(ql <= l && r <= qr) return tour[x];
	int mid = (l + r) >> 1;
	pair<int, int> L = f(x * 2 + 1, l, mid, ql, qr);
	pair<int, int> R = f(x * 2 + 2, mid + 1, r, ql, qr);
	return max(L, R);
}
void con(int x, int l, int r){
	if(l == r){
		tour[x] = {h[l], l};
		return ;
	}
	int mid = (l + r) >> 1;
	con(x * 2 + 1, l, mid);
	con(x * 2 + 2, mid + 1, r);
	tour[x] = max(tour[x * 2 + 1], tour[x * 2 + 2]);
}

void init(int _n, vector<int> _h){
	n = _n; h = _h;
	h.push_back(n);
	con(0, 0, n - 1);
	stack<int> s;

	for(int i = 0; i < n; ++i){
		while(!s.empty() && h[s.top()] < h[i]) s.pop();
		if(s.empty()) prv[i] = -1;
		else prv[i] = s.top();
		s.push(i);
	}

	while(!s.empty()) s.pop();

	for(int i = n - 1; i >= 0; --i){
		while(!s.empty() && h[s.top()] < h[i]) s.pop();
		if(s.empty()) nxt[i][0] = n;
		else nxt[i][0] = s.top();
		s.push(i);

		prv_max[i][0] = h[i];
	}

	for(int p = 0; p < n; ++p){
		if(nxt[p][0] == n && prv[p] == -1) jump[p][0] = n;
		else if(nxt[p][0] == n) jump[p][0] = prv[p];
		else if(prv[p] == -1) jump[p][0] = nxt[p][0];
		else if(h[nxt[p][0]] > h[prv[p]]) jump[p][0] = nxt[p][0];
		else jump[p][0] = prv[p];
		
		if(nxt[p][0] == n && prv[p] == -1) max_reachable[p][0] = n;
		else if(nxt[p][0] == n) max_reachable[p][0] = p;
		else max_reachable[p][0] = nxt[p][0];
	}
	
	jump[n][0] = max_reachable[n][0] = n;
	
	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i <= n; ++i){
			jump[i][j] = jump[jump[i][j - 1]][j - 1];
			max_reachable[i][j] = max(max_reachable[i][j - 1], max_reachable[jump[i][j - 1]][j - 1]);
		}
	}

	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i < n; ++i){
			if(nxt[i][j - 1] == n) nxt[i][j] = n;
			else nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];

			prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, i - (1 << j - 1))][j - 1]);
		}
	}
}

int minimum_jumps(int a, int b, int c, int d){
	pair<int, int> maks = f(0, 0, n - 1, b + 1, d);
	if(maks.Y < c) return -1;
	int idx = b;
	for(int i = LOG - 1; i >= 0; --i){
		if(idx - (1 << i) >= a - 1 && prv_max[idx][i] < maks.X){
			idx -= 1 << i;
		}
	}
	++idx;
	if(idx > b) return -1;
	int node = f(0, 0, n - 1, idx, b).Y, ret = 0;
	
	assert(a <= node && node <= b);
	
	for(int i = LOG - 1; i >= 0; --i){
		if(max_reachable[node][i] < c && h[jump[node][i]] < maks.X){
			node = jump[node][i];
			ret += 1 << i;
		}
	}
	assert(node < c);
	for(int i = LOG - 1; i >= 0; --i){
		if(nxt[node][i] < c){
			node = nxt[node][i];
			ret += 1 << i;
		}
	}
	assert(node < c);
	if(nxt[node][0] > d) return -1;
	assert(nxt[node][0] >= c);
	assert(h[nxt[node][0]] <= maks.X);
	return ret + 1;
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp:8:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    8 | const int OFF = 1 << LOG + 1;
      |                      ~~~~^~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:84:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   84 |    prv_max[i][j] = max(prv_max[i][j - 1], prv_max[max(0, i - (1 << j - 1))][j - 1]);
      |                                                                    ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19