제출 #569674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569674		codr0	밀림 점프 (APIO21_jumps)	C++14	100 / 100	1291 ms	49456 KiB

jumps

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#include "jumps.h"
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';

using namespace std;
const int N=2e5+4;
const int lg=20;
int pw[lg],SM[lg][N],RR[N],LL[N],opt[lg][N],R[lg][N];

	int MX(int l,int r){
		if(l>r) return 0;
		int LG=31-__builtin_clz(r-l+1);
		return max(SM[LG][l],SM[LG][r-pw[LG]+1]);
	}

	void init(int n,vector<int> H){
		pw[0]=1; FOR(j,1,lg-1) pw[j]=pw[j-1]*2;
		int h[n+1];
		FOR(i,1,n) h[i]=H[i-1];
		FOR(i,1,n) SM[0][i]=h[i];
		FOR(j,1,lg-1) FOR(i,1,n-pw[j]+1) SM[j][i]=max(SM[j-1][i],SM[j-1][i+pw[j-1]]);
		vector<int> vc;
		FOR(i,1,n){
			while(!vc.empty()&&vc.back()<h[i]){
				RR[vc.back()]=h[i];
				vc.pop_back();
			}
			vc.pb(h[i]);
		}
		vc.clear();
		FORR(i,n,1){
			while(!vc.empty()&&vc.back()<h[i]){
				LL[vc.back()]=h[i];
				vc.pop_back();
			}
			vc.pb(h[i]);
		}
		FOR(i,1,n) opt[0][i]=max(LL[i],RR[i]);
		FOR(j,1,lg-1) FOR(i,1,n) opt[j][i]=opt[j-1][opt[j-1][i]];
		FOR(i,1,n) R[0][i]=RR[i];
		FOR(j,1,lg-1) FOR(i,1,n) R[j][i]=R[j-1][R[j-1][i]];
	}

	int minimum_jumps(int A,int B,int C,int D){
		A++; B++; C++; D++;
		int bmx=MX(C,D);
		int mx=MX(B+1,C-1);
		int l=A-1,r=B+1;
		while(r-l>1){
			int mid=(r+l)/2;
			if(MX(mid,B)<=bmx) r=mid;
			else l=mid;
		}
		if(r==B+1) return -1;
		if(mx>bmx) return -1;
		int amx=MX(r,B);
		if(amx>mx) return 1;
		int rt=0;
		int v=amx;
		FORR(j,lg-1,0) if(opt[j][v]&&opt[j][v]<mx){
			v=opt[j][v];
			rt+=pw[j];
		}
		if((LL[v]>mx&&LL[v]<bmx)||(RR[v]==mx)) return (rt+2);
		FORR(j,lg-1,0) if(R[j][v]&&R[j][v]<mx){
			v=R[j][v];
			rt+=pw[j];
		}
		return (rt+2);
	}

• 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