제출 #1098344

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

jumps

#include "jumps.h"
int pie(int army){return (1<<army);}
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int lef[200000][18],rig[200000][18],smart[200000][18][2];

int cal(int pos,int C,int D){
	int ans=0;
	int mn=pos,mx=pos;
	for(int i=18-1;i>=0;i--){
		if(max(smart[mx][i][1],smart[mn][i][1])>=C)continue;
		ans+=pie(i);
		int tmp;
		tmp=min(smart[mx][i][0],smart[mn][i][0]);
		mx=max(smart[mx][i][1],smart[mn][i][1]);
		mn=tmp;
	}
	if((smart[mx][0][1]>=C&&smart[mx][0][1]<=D)||(smart[mn][0][1]>=C&&smart[mn][0][1]<=D))return ans+1;
	for(int i=18-1;i>=0;i--){
		if(rig[mx][i]>=C)continue;
		ans+=pie(i);
		mx=rig[mx][i];
	}
	mx=rig[mx][0];
	if(mx>=C&&mx<=D)return ans+1;
	return -1;
}

int minimum_jumps(int A,int B,int C,int D){
	int ans=cal(B,C,D);
	if(ans==-1)return ans;
	int pos=B;
	for(int i=18-1;i>=0;i--){
		if(lef[pos][i]<A)continue;
		int res=cal(lef[pos][i],C,D);
		if(res==-1)continue;
		pos=lef[pos][i];
		ans=res;
	}
	return ans;
}

void init(int N,vector<int> H){
	vector<int>sta;
	for(int i=0;i<N;i++){
		while(sta.size()&&H[sta.back()]<H[i])sta.pop_back();
		if(sta.size()==0)lef[i][0]=i;
		else lef[i][0]=sta.back();
		sta.pb(i);
	}
	sta.clear();
	for(int i=N-1;i>=0;i--){
		while(sta.size()&&H[sta.back()]<H[i])sta.pop_back();
		if(sta.size()==0)rig[i][0]=i;
		else rig[i][0]=sta.back();
		sta.pb(i);
	}
	for(int i=0;i<N;i++){
		smart[i][0][0]=lef[i][0];
		smart[i][0][1]=rig[i][0];
	}
	for(int i=1;i<18;i++){
		for(int j=0;j<N;j++){
			lef[j][i]=lef[lef[j][i-1]][i-1];
			rig[j][i]=rig[rig[j][i-1]][i-1];
			smart[j][i][0]=min(smart[smart[j][i-1][0]][i-1][0],smart[smart[j][i-1][1]][i-1][0]);
			smart[j][i][1]=max(smart[smart[j][i-1][0]][i-1][1],smart[smart[j][i-1][1]][i-1][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