제출 #676352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676352		penguin133	밀림 점프 (APIO21_jumps)	C++17	39 / 100	1124 ms	55092 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
 
int n, flag;
int X[200005], Y[200005], h[200005];
int par[20][200005], par2[20][200005];
 
struct node{
	int s,e,m, val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			val = min(l->val, r->val);
		}
		else val = h[s];
	}
	
	int find(int a, int b, int c){
		if(s == e){
			return (val <= c ? s : -1);
		}
		if(b <= m)return l->find(a, b, c);
		else if(a > m)return r->find(a, b, c);
		else{
			int res = -1;
			if(r->val <= c)res = max(res, r->find(m+1, b, c));
			if(res == -1 && l->val <= c)res = max(res, l->find(a, m, c));
			return res;
		}
	}
	
}*root;
 
 
void init(int N, vector<int> H){
	n = N;
	stack<int>s;
	for(int i=0;i<n;i++){
		h[i] = H[i];
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		X[i] = (s.empty() ? -1 : s.top());
		s.push(i);
	}
	flag = 1;
	for(int i=0;i<n;i++)if(H[i] != i + 1)flag= 0;
	while(!s.empty())s.pop();
	for(int i=n-1;i>=0;i--){
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		Y[i] = (s.empty() ? -1 : s.top());
		s.push(i);
	}
	root = new node(0, n-1);
	for(int i=0;i<n;i++){
		if(X[i] == -1 && Y[i] == -1)par[0][i] = par2[0][i] = -1;
		else if(X[i] == -1)par[0][i] = Y[i], par2[0][i] = -1;
		else if(Y[i] == -1)par[0][i] = X[i], par2[0][i] = -1;
		else par[0][i] = (H[X[i]] > H[Y[i]] ? X[i] : Y[i]), par2[0][i] = (par[0][i] == X[i] ? Y[i] : X[i]);
	}
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par[i][j] = (par[i-1][j] == -1 ? -1 : par[i-1][par[i-1][j]]);
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par2[i][j] = (par2[i-1][j] == -1 ? -1 : par2[i-1][par2[i-1][j]]);
}
 
int minimum_jumps(int a, int b, int c, int d){
	if(flag){
		if(a > d)return -1;
		else if(b >= c || a >= d)return 0;
		else return c-b;
	}
	if(c == d){
		int ans = 0, tmp = root->find(a, b, h[c]);
      if(tmp == -1)return -1;
		for(int i=19;i>=0;i--)if(par[i][tmp] != -1 && h[par[i][tmp]] <= h[c])tmp = par[i][tmp], ans += (1 << i);
		for(int i=19;i>=0;i--)if(par2[i][tmp] != -1 && h[par2[i][tmp]] <= h[c])tmp = par2[i][tmp], ans += (1 << i);
		return (tmp == c ? ans : -1);
	}
	queue<int>q;
	int dist[n+1];
	for(int i=0;i<n;i++)dist[i] = 1e9;
	for(int i=a;i<=b;i++)dist[i] = 0, q.push(i);
	while(!q.empty()){
		int x = q.front();q.pop();
		if(X[x] != -1 && dist[X[x]] > dist[x] + 1)dist[X[x]] = dist[x] + 1, q.push(X[x]);
		if(Y[x] != -1 && dist[Y[x]] > dist[x] + 1)dist[Y[x]] = dist[x] + 1, q.push(Y[x]);
	}
	int mini = 1e9;
	for(int i=c;i<=d;i++)mini = min(mini, dist[i]);
	return (mini == 1e9 ? -1 : mini);
}

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