Submission #413540

#	Time	Username	Problem	Language	Result	Execution time	Memory
413540		AmineWeslati	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	2489 ms	48212 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef vector<int>vi; 
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

typedef pair<int,int>pi;
typedef vector<pi>vpi;
#define fi first
#define se second
#define eb emplace_back

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void ckmin(int &x, int y){x=min(x,y);}
//----------------------
const ll INF=1e9;
const int MX=2e5+10;
const int LOG=25;

int N; 
vi a(MX,INF);

//----------

vi t(MX*4);	
int combine(int i, int j){
	if(i==-1) return j; 
	if(j==-1) return i; 
	if(a[i]>=a[j]) return i; 
	return j; 
}
void build(int pos=1, int tl=1, int tr=N){
	if(tl==tr){
		t[pos]=tl;
		return; 
	}

	int tm=(tl+tr)/2;
	build(pos*2,tl,tm);
	build(pos*2+1,tm+1,tr);

	t[pos]=combine(t[pos*2],t[pos*2+1]);
}
int get(int l, int r, int pos=1, int tl=1, int tr=N){
	if(l>r) return -1;
	if(l==tl && r==tr) return t[pos]; 

	int tm=(tl+tr)/2;
	return combine(get(l,min(r,tm),pos*2,tl,tm),
		get(max(tm+1,l),r,pos*2+1,tm+1,tr));
}
//-----------


int jump[MX][LOG],jumpRight[MX][LOG];

bool cmp(int i, int j){
	return a[i]>a[j];
}

vi lft,rgt;
vi vec; 
void precompute(){
	lft.assign(N+2,0); rgt.assign(N+2,N+1);

	vi st; 
	FOR(i,1,N+1){
		while(sz(st) && a[st.back()]<a[i]) st.pop_back();
		if(sz(st)) lft[i]=st.back();

		st.pb(i);
	}
	st.clear();

	ROF(i,1,N+1){
		while(sz(st) && a[st.back()]<a[i]) st.pop_back();
		if(sz(st)) rgt[i]=st.back();

		st.pb(i);
	}

	vec.resize(N);
	iota(all(vec),1);
	sort(all(vec),cmp);

	FOR(i,0,LOG){
		jump[0][i]=0;
		jumpRight[0][i]=0;
		jump[N+1][i]=N+1;
		jumpRight[N+1][i]=N+1;
	}

	a[0]=a[N+1]=-1;
	for(int i: vec){
		jumpRight[i][0]=rgt[i];

		if(a[rgt[i]]>=a[lft[i]]) jump[i][0]=rgt[i];
		else jump[i][0]=lft[i];

		FOR(b,1,LOG){
			jump[i][b]=jump[jump[i][b-1]][b-1];
			jumpRight[i][b]=jumpRight[jumpRight[i][b-1]][b-1];
		}
	}
	a[0]=a[N+1]=INF; 

	reverse(all(vec));
}

void init(int N, vi H){
	::N=N; 
	FOR(i,0,N) a[i+1]=H[i];

	build();
	precompute();
}

int cnt=0;
int minimum_jumps(int A, int B, int C, int D){
	A++; B++; C++; D++;

	//-----------
	/*cnt++;
	if((N<=2000 && cnt<=2000) || cnt<=5){
		vi dp(N+2,INF);
		FOR(i,A,B+1) dp[i]=0;

		for(int i: vec){
			ckmin(dp[rgt[i]],dp[i]+1);
			ckmin(dp[lft[i]],dp[i]+1);
		}

		int ans=INF; 
		FOR(i,C,D+1) ckmin(ans,dp[i]);
		if(ans==INF) ans=-1;
		return ans; 
	}*/
	///////////

	int e=get(C,D),s;

	int l=1,r=e; 
	while(l<=r){
		int m=(l+r)/2;
		if(a[get(m,e)]<=a[e]){
			s=m; 
			r=m-1;
		}
		else l=m+1;
	}
	if(s>B) return -1;
	
	l=max(s,A);
	r=B; 
	s=get(l,r);

	if(C==B+1) return 1;	

	int ee=e; 
	e=get(B+1,C-1);
	if(a[e]<a[s]) return 1;

	int ans=2;
	ROF(i,0,LOG) if(a[jump[s][i]]<a[e]){
		s=jump[s][i];
		ans+=(1<<i);
	}
	if(a[jump[s][0]]<=a[ee]) return ans; 

	ROF(i,0,LOG) if(a[jumpRight[s][i]]<a[e]){
		s=jumpRight[s][i];
		ans+=(1<<i);
	}
	return ans; 
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:148:17: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |  int e=get(C,D),s;
      |                 ^

• 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