oj.uz

Submission #525323

# Submission time Handle Problem Language Result Execution time Memory
525323 2022-02-11T10:11:55 Z Koosha_mv Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1171 ms 37664 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){
		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);
	}
	//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 0 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 156 ms 30016 KB Output is correct
4 Correct 1147 ms 37448 KB Output is correct
5 Correct 843 ms 19104 KB Output is correct
6 Correct 1062 ms 37424 KB Output is correct
7 Correct 955 ms 25672 KB Output is correct
8 Correct 1171 ms 37340 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Incorrect 3 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 0 ms 584 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Incorrect 3 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 1 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 46 ms 30120 KB Output is correct
6 Correct 58 ms 37664 KB Output is correct
7 Correct 29 ms 19496 KB Output is correct
8 Correct 78 ms 37352 KB Output is correct
9 Correct 8 ms 6088 KB Output is correct
10 Correct 59 ms 37400 KB Output is correct
11 Correct 51 ms 37408 KB Output is correct
12 Correct 46 ms 37428 KB Output is correct
13 Correct 48 ms 37440 KB Output is correct
14 Correct 54 ms 37416 KB Output is correct
15 Incorrect 76 ms 37364 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 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 196 ms 17436 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 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 196 ms 17436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 156 ms 30016 KB Output is correct
4 Correct 1147 ms 37448 KB Output is correct
5 Correct 843 ms 19104 KB Output is correct
6 Correct 1062 ms 37424 KB Output is correct
7 Correct 955 ms 25672 KB Output is correct
8 Correct 1171 ms 37340 KB Output is correct
9 Correct 0 ms 584 KB Output is correct
10 Correct 0 ms 584 KB Output is correct
11 Correct 0 ms 584 KB Output is correct
12 Correct 1 ms 584 KB Output is correct
13 Incorrect 3 ms 584 KB Output isn't correct
14 Halted 0 ms 0 KB -