제출 #1311072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311072		vtnoo	밀림 점프 (APIO21_jumps)	C++20	4 / 100	474 ms	54472 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int,int>
using namespace std;
const int MAXN=2e5+5,LOG=20,INF=1e9;
int h[MAXN],sl[MAXN],sr[MAXN],upf[MAXN][LOG],upl[MAXN][LOG],upr[MAXN][LOG],n;
vi st;
void init(int N, std::vector<int> H) {
	n=N;
	stack<ii>mn;
	L(i,0,N-1){
		while(sz(mn)&&mn.top().fst<=H[i]){
			mn.pop();
		}
		sl[i]=sz(mn)?mn.top().snd:i;
		mn.push({H[i],i});
	}
	while(sz(mn))mn.pop(); 
	R(i,N-1,0){
		while(sz(mn)&&mn.top().fst<=H[i]){
			mn.pop();
		}
		sr[i]=sz(mn)?mn.top().snd:i;
		mn.push({H[i],i});
	}
	L(i,0,N-1)h[i]=H[i];
	L(i,0,N-1){
		if(h[sl[i]]>h[sr[i]]){
			upf[i][0]=sl[i];
		}else{
			upf[i][0]=sr[i];
		}
		upl[i][0]=sl[i];
		upr[i][0]=sr[i];
	}
	L(i,1,LOG-1){
		L(j,0,N-1){
			upl[j][i]=upl[upl[j][i-1]][i-1];
			upr[j][i]=upr[upr[j][i-1]][i-1];
			upf[j][i]=upf[upf[j][i-1]][i-1];
		}
	}
	st.resize(n*2);
	L(i,0,n-1){
		st[i+n]=h[i];
	}
	R(i,n-1,1){
		st[i]=max(st[i*2],st[i*2+1]);
	}
}

int que(int l,int r){
	int mx=0;
	l+=n,r+=n;
	while(l<r){
		if(l%2)mx=max(mx,st[l++]);
		if(r%2)mx=max(mx,st[--r]);
		r/=2;l/=2;
	}
	return mx;
}

int minimum_jumps(int A, int B, int C, int D) {
	int lim=que(C,D+1),lim2=que(B+1,C);
	//~ cout<<lim<<" "<<lim2<<endl;
	int u=B;
	R(i,LOG-1,0){
		if(upl[u][i]==u)continue;
		if(upl[u][i]<A)continue;
		if(h[upl[u][i]]<lim){
			u=upl[u][i];
		}
	}
	//~ cout<<u<<endl;
	if(C<=sr[u]&&sr[u]<=D)return 1;
	int ans=0;
	R(i,LOG-1,0){
		if(upf[u][i]==u)continue;
		if(h[upf[u][i]]<=lim2){
			u=upf[u][i];
			ans+=(1<<i);
		}
	}
	//~ cout<<u<<endl;
	R(i,LOG-1,0){
		if(upr[u][i]==u)continue;
		if(upr[u][i]<C){
			u=upr[u][i];
			ans+=(1<<i);
		}
	}
	//~ cout<<u<<endl;
	if(C<=sr[u]&&sr[u]<=D)return ans+1;
	else return -1;
}

//~ int main(){
	//~ int N,Q;cin>>N>>Q;
	//~ vi H(N);
	//~ L(i,0,N-1)cin>>H[i];
	//~ init(N,H);
	//~ while(Q--){
		//~ int A,B,C,D;cin>>A>>B>>C>>D;
		//~ cout<<minimum_jumps(A,B,C,D)<<endl;
	//~ }
//~ }

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