Submission #1021017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021017		ttamx	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	947 ms	48488 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int N=2e5+5;
const int LG=18;
 
int n;
int a[N];
int pre[N],nxt[N],best[N];
 
struct Doubling{
	int dp[N][LG];
	void build(int* a){
		for(int i=0;i<=n+1;i++)dp[i][0]=a[i];
		for(int j=1;j<LG;j++)for(int i=0;i<=n+1;i++)dp[i][j]=dp[dp[i][j-1]][j-1];
	}
	template<class F>
	pair<int,int> query(int x,F f){
		int res=0;
		for(int i=LG-1;i>=0;i--)if(f(dp[x][i])){
			x=dp[x][i];
			res|=1<<i;
		}
		return {x,res};
	}
}l,r,h;
 
void init(int _n,vector<int> _a){
	n=_n;
	for(int i=1;i<=n;i++)a[i]=_a[i-1];
	a[0]=a[n+1]=n+1;
	stack<int> s;
	for(int i=1;i<=n;i++){
		while(!s.empty()&&a[s.top()]<a[i])s.pop();
		pre[i]=s.empty()?0:s.top();
		s.emplace(i);
	}
	pre[0]=pre[n+1]=0;
	while(!s.empty())s.pop();
	for(int i=n;i>=1;i--){
		while(!s.empty()&&a[s.top()]<a[i])s.pop();
		nxt[i]=s.empty()?n+1:s.top();
		s.emplace(i);
	}
	nxt[0]=nxt[n+1]=n+1;
	for(int i=1;i<=n;i++)best[i]=a[pre[i]]>a[nxt[i]]?pre[i]:nxt[i];
	best[0]=best[n+1]=0;
	l.build(pre);
	r.build(nxt);
	h.build(best);
}
 
int minimum_jumps(int a,int b,int c,int d){
	a++,b++,c++,d++;
	int u=b;
	u=l.query(u,[&](int x){return x>=a&&nxt[x]<=d;}).first;
	if(c<=nxt[u]&&nxt[u]<=d)return 1;
	int ans,cost;
	tie(u,ans)=h.query(u,[&](int x){return nxt[x]<c;});
	if(nxt[best[u]]<=d)return ans+2;
	tie(u,cost)=r.query(u,[&](int x){return x<c;});
	u=nxt[u];
	return c<=u&&u<=d?ans+cost+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