제출 #946376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946376		amirhoseinfar1385	밀림 점프 (APIO21_jumps)	C++17	21 / 100	1648 ms	8384 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=20;
int inf=1e9;
int n,all[maxn],fr[maxn],fl[maxn],sp[lg][maxn],spr[lg][maxn];

void pre(){
	//cout<<"slaam1"<<endl;
	all[0]=all[n+1]=inf;
	vector<int>v;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		while((int)v.size()>0&&all[v.back()]<=all[i]){
			v.pop_back();
		}
		fl[i]=v.back();
		v.push_back(i);
	}
	v.clear();
	v.push_back(n+1);
//	//cout<<"slaam2"<<endl;
	for(int i=n;i>=1;i--){
		while((int)v.size()>0&&all[v.back()]<=all[i]){
			v.pop_back();
		}
		fr[i]=v.back();
		v.push_back(i);
	}
//	//cout<<"dov"<<endl;
	for(int i=1;i<=n;i++){
//		//cout<<i<<" "<<fr[i]<<" "<<fl[i]<<endl;
		spr[0][i]=fr[i];
		if(all[fr[i]]>=all[fl[i]]){
			sp[0][i]=fr[i];
		}else{
			sp[0][i]=fl[i];
		}
	}
//	//cout<<"wtf"<<endl;
}

void init(int N,vector<int> H) {
	n=N;
	for(int i=1;i<=n;i++){
		all[i]=H[i-1];
	}
	pre();
}

int cal(int a,int b,int c,int mx){
	//cout<<"injy: "<<a<<" "<<b<<" "<<c<<" "<<mx<<" "<<all[a]<<endl;
	if(all[a]>mx){
		return inf;
	}
	if(a>=b&&a<=c){
		return 0;
	}
	if(spr[0][a]>=b&&spr[0][a]<=c){
		return 1;
	}
	if(all[sp[0][a]]<=mx){
		return cal(sp[0][a],b,c,mx)+1;
	}
	return cal(spr[0][a],b,c,mx)+1;
}

int solve(int a,int b,int c,int d){
	int mxb=all[c];
	for(int i=c;i<=d;i++){
		mxb=max(mxb,all[i]);
	}
	int res=inf;
	for(int i=a;i<=b;i++){
		res=min(res,cal(i,c,d,mxb));
	}
	if(res==inf){
		res=-1;
	}
	return res;
}

int minimum_jumps(int A, int B, int C, int D) {
 	A++;
 	B++;
 	C++;
 	D++;
 	return solve(A,B,C,D);
}

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