Submission #413363

#	Time	Username	Problem	Language	Result	Execution time	Memory
413363		keta_tsimakuridze	Rainforest Jumps (APIO21_jumps)	C++14	81 / 100	4081 ms	50912 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>

using namespace std;
const int N = 2e5+5;
int r[N],l[N],n,dist[N],F,ans,aft[2][N][20],Lg,a[N],tree[4*N],idx[N];
vector<int>V[N];
void build(int u,int l,int r){
	if(l==r) {
		tree[u] = a[l];
		return;
	}
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	tree[u] = max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) return tree[u];
	int mid = (l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void init(int NN, std::vector<int> H) {
	n=NN;
	for(int i=0;i<n;i++){
		aft[0][i][0] = -1;
		aft[1][i][0] = -1;
		a[i]=H[i];
		idx[a[i]] = i;
		int x = i-1;
		if(H[i]!=i+1) F=1;
		while(x>=0 && H[x]<=H[i]) x = l[x];
		l[i] = x;
		if(x>=0) V[i].push_back(x);
	}
	build(1,0,n-1);
	for(int i=n-1;i>=0;i--){
		int x = i+1;
		while(x<n && H[x]<H[i]) x = r[x];
		r[i] = x;
		if(x<n) V[i].push_back(x);
		if(r[i]<n && l[i]>=0) {
			aft[1][i][0] = r[i];
			aft[0][i][0] = l[i];
			if(H[r[i]] < H[l[i]]) swap(aft[1][i][0],aft[0][i][0]);
		}
		else if(r[i]<n) {
			aft[1][i][0] = r[i];
		}
		else if(l[i]>=0){
			aft[1][i][0] = l[i];
		}
	//	cout<<i<<"__"<<aft[0][i][0]<<" "<<aft[1][i][0]<<endl;
	}
	Lg = log2(n)+1;
	for(int f=0;f<2;f++){
		for(int j=1;j<=Lg;j++)
		for(int i=0;i<n;i++) {
			if(aft[f][i][j-1]==-1) aft[f][i][j] = -1;
			else aft[f][i][j]=aft[f][aft[f][i][j-1]][j-1];
		}
	}
}
int Up(int u,int f,int b){ 
	for(int i=Lg;i>=0;i--){
		if(aft[f][u][i]!=-1 && a[aft[f][u][i]] <= b ) ans += (1<<i),u=aft[f][u][i];
	}
	return u;
}
int minimum_jumps(int A, int B, int C, int D) {
	if(!F) {
		if(A>D ) return -1;
		if(B<=C) return C-B;
		return 0;
	}
	else if( C==D){
		ans = 0;
		if(A<=C && C<=B) return 0;
		if(B<C) {
			if(l[D] >= B) return -1;
			A = getans(1,max(A,l[D]+1),B,0,n-1);
		}
		else  {
			if(r[D] <= A) return -1;
			A= getans(1,A,min(B,r[D]-1),0,n-1);
		}
		A = idx[A];
	//	cout<<ans<<endl;
		if(Up(Up(A,1,a[C]),0,a[C]) == C) return ans;
		return -1;
	}
	else {
	
	queue<pii>q;
	int Inf=n+5;
	for(int i=0;i<n;i++) dist[i] = Inf;
	for(int i=A;i<=B;i++){
		q.push({0,i});
		dist[i] = 0;
	}
	int ans=Inf;
	while(q.size()){
		int u = q.front().s;
		int d=q.front().f;
		q.pop(); //cout<<u<<"da"<<d<<endl;
		if(d>dist[u]) continue;
		if(u>=C && u<=D) ans=min(ans,d);
		for(int i=0;i<V[u].size();i++) {
			if(dist[V[u][i]]>d+1){
				dist[V[u][i]]=d+1;
				q.push({d+1,V[u][i]});
			}
		}
	}
  if(ans!=Inf) return ans;
  return -1;}
}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~

• 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: 0 / 19