oj.uz

Submission #413539

# Submission time Handle Problem Language Result Execution time Memory
413539 2021-05-28T21:14:18 Z AmineWeslati Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2245 ms 48160 KB 
#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;

	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);
	}
	ROF(i,0,LOG) if(a[jumpRight[s][i]]<a[e]){
		s=jumpRight[s][i];
		ans+=(1<<i);
	}
	return ans; 
}

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4168 KB Output is correct
3 Correct 300 ms 39112 KB Output is correct
4 Correct 2245 ms 48076 KB Output is correct
5 Correct 1917 ms 26448 KB Output is correct
6 Correct 2196 ms 48052 KB Output is correct
7 Correct 1493 ms 34284 KB Output is correct
8 Correct 2069 ms 48160 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4236 KB Output is correct
3 Correct 3 ms 4168 KB Output is correct
4 Correct 3 ms 4168 KB Output is correct
5 Correct 5 ms 4168 KB Output is correct
6 Incorrect 4 ms 4168 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4236 KB Output is correct
3 Correct 3 ms 4168 KB Output is correct
4 Correct 3 ms 4168 KB Output is correct
5 Correct 5 ms 4168 KB Output is correct
6 Incorrect 4 ms 4168 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4236 KB Output is correct
2 Correct 3 ms 4216 KB Output is correct
3 Correct 3 ms 4168 KB Output is correct
4 Correct 3 ms 4168 KB Output is correct
5 Correct 135 ms 38796 KB Output is correct
6 Correct 170 ms 47144 KB Output is correct
7 Correct 78 ms 26180 KB Output is correct
8 Correct 176 ms 47176 KB Output is correct
9 Correct 27 ms 10700 KB Output is correct
10 Correct 186 ms 47300 KB Output is correct
11 Correct 112 ms 48096 KB Output is correct
12 Correct 101 ms 47988 KB Output is correct
13 Incorrect 103 ms 47852 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4168 KB Output is correct
3 Correct 2 ms 4168 KB Output is correct
4 Incorrect 392 ms 23796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4168 KB Output is correct
3 Correct 2 ms 4168 KB Output is correct
4 Incorrect 392 ms 23796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4168 KB Output is correct
2 Correct 3 ms 4168 KB Output is correct
3 Correct 300 ms 39112 KB Output is correct
4 Correct 2245 ms 48076 KB Output is correct
5 Correct 1917 ms 26448 KB Output is correct
6 Correct 2196 ms 48052 KB Output is correct
7 Correct 1493 ms 34284 KB Output is correct
8 Correct 2069 ms 48160 KB Output is correct
9 Correct 3 ms 4168 KB Output is correct
10 Correct 3 ms 4236 KB Output is correct
11 Correct 3 ms 4168 KB Output is correct
12 Correct 3 ms 4168 KB Output is correct
13 Correct 5 ms 4168 KB Output is correct
14 Incorrect 4 ms 4168 KB Output isn't correct
15 Halted 0 ms 0 KB -