Submission #1097988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097988		PieArmy	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	966 ms	60040 KiB

jumps

#include "jumps.h"
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n;

int lef[200002][18],rig[200002][18],smart[200002][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){
	A++;B++;C++;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){
	n=N;
	int arr[n+2];
	for(int i=1;i<=n;i++){
		arr[i]=H[i-1];
	}
	vector<int>sta;
	for(int i=1;i<=n;i++){
		while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
		if(sta.size()==0)lef[i][0]=i;
		else lef[i][0]=sta.back();
		sta.pb(i);
	}
	while(sta.size())sta.pop_back();
	for(int i=n;i>=1;i--){
		while(sta.size()&&arr[sta.back()]<arr[i])sta.pop_back();
		if(sta.size()==0)rig[i][0]=i;
		else rig[i][0]=sta.back();
		sta.pb(i);
	}
	for(int i=1;i<18;i++){
		for(int j=1;j<=n;j++){
			lef[j][i]=lef[lef[j][i-1]][i-1];
			rig[j][i]=rig[rig[j][i-1]][i-1];
		}
	}
	for(int i=1;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=1;j<=n;j++){
			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