oj.uz

Submission #525322

# Submission time Handle Problem Language Result Execution time Memory
525322 2022-02-11T10:02:57 Z Koosha_mv Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1148 ms 37524 KB 
#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_(i,n,0){
		f(l,1,lg){
			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 || a[get(B+1,C)]>a[posr]){
		return -1;
	}
	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);
	}
	//cout<<ans<<" "<<res<<endl;
	return ans+res;
}
/*
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int n;
	n=7;
	a[0]=3,a[1]=2,a[2]=1,a[3]=6,a[4]=4,a[5]=5,a[6]=7;
	init(n,a);
	while(1){
		int A,B,C,D;
		cin>>A>>B>>C>>D;
		cout<<minimum_jumps(A,B,C,D)<<endl;
	}
}
*/
/*
7
3 2 1 6 4 5 7

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 155 ms 29832 KB Output is correct
4 Correct 1148 ms 37312 KB Output is correct
5 Correct 978 ms 19104 KB Output is correct
6 Correct 1036 ms 37368 KB Output is correct
7 Correct 907 ms 25752 KB Output is correct
8 Correct 1014 ms 37392 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 45 ms 30180 KB Output is correct
6 Correct 56 ms 37312 KB Output is correct
7 Correct 37 ms 19380 KB Output is correct
8 Correct 56 ms 37404 KB Output is correct
9 Correct 9 ms 6088 KB Output is correct
10 Correct 59 ms 37524 KB Output is correct
11 Correct 48 ms 37424 KB Output is correct
12 Correct 55 ms 37336 KB Output is correct
13 Correct 46 ms 37392 KB Output is correct
14 Correct 55 ms 37392 KB Output is correct
15 Incorrect 59 ms 37424 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 237 ms 17428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 237 ms 17428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 155 ms 29832 KB Output is correct
4 Correct 1148 ms 37312 KB Output is correct
5 Correct 978 ms 19104 KB Output is correct
6 Correct 1036 ms 37368 KB Output is correct
7 Correct 907 ms 25752 KB Output is correct
8 Correct 1014 ms 37392 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 0 ms 584 KB Output is correct
12 Correct 0 ms 584 KB Output is correct
13 Incorrect 2 ms 584 KB Output isn't correct
14 Halted 0 ms 0 KB -