Submission #525658

#	Time	Username	Problem	Language	Result	Execution time	Memory
525658		Koosha_mv	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1311 ms	37536 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int maxn=1e6+99,lg=20;
 
int n,t,a[maxn],pos[maxn],seg[maxn],L[maxn],R[lg][maxn],par[lg][maxn];
 
void build(){
	f(i,0,n){
		seg[i+n]=a[i];
	}
	f_(i,n-1,1){
		seg[i]=max(seg[i<<1],seg[i<<1|1]);
	}
	f(i,0,n){
		L[i]=i-1;
		while(L[i]!=-1 && a[L[i]]<a[i]){
			L[i]=L[L[i]];
		}
	}
	R[0][n]=n;
	f_(i,n-1,0){
		R[0][i]=i+1;
		while(R[0][i]!=n && a[i]>a[R[0][i]]){
			R[0][i]=R[0][R[0][i]];
		}
	}
	f(i,0,n){
		if(a[i]==n-1){
			par[0][i]=i;
		}
		else{
			if(L[i]==-1 || (R[0][i]!=n && a[R[0][i]]>a[L[i]])){
				par[0][i]=R[0][i];
			}
			else{
				par[0][i]=L[i];
			}
		}
	}
	f(l,1,lg){
		f_(i,n,0){
			R[l][i]=R[l-1][R[l-1][i]];
			par[l][i]=par[l-1][par[l-1][i]];
		}
	}
}
int get(int l,int r){
	int mx=0;
	for(l+=n,r+=n;l<r;l>>=1,r>>=1){
		if(l&1){
			maxm(mx,seg[l++]);
		}
		if(r&1){
			maxm(mx,seg[--r]);
		}
	}
	return pos[mx];
}
int getdist(int x,int t){
	int res=1;
	f_(l,lg-1,0){
		if(R[l][x]<t){
			x=R[l][x];
			res+=(1<<l);
		}
	}
	return res;
}
void init(int N,vector<int> H){
	n=N;
	f(i,0,n) a[i]=--H[i],pos[a[i]]=i;
	build();
}
int minimum_jumps(int A, int B, int C, int D){
	int posr=get(C,D+1),ans=0,res=0,now;
	maxm(A,L[posr]+1);
	if(B<A){
		return -1;
	}
	if(a[get(B+1,C)]>a[posr]){
		assert(0);
	}
	now=get(A,B+1);
	if(C<=R[0][now]){
		return 1;
	}
	f_(l,lg-1,0){
		int x=par[l][now];
		if(R[0][x]<C){
			ans+=(1<<l);
			now=x;
		}
	}
	res=getdist(now,C);
	now=par[0][now];
	if(a[now]<a[posr]){
		minm(res,getdist(now,C)+1);
	}
	return ans+res;
}

• 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