oj.uz

Submission #981164

# Submission time Handle Problem Language Result Execution time Memory
981164 2024-05-13T00:49:44 Z Darren0724 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 37288 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v,a,b,pl;
int jump[20][200005];
int jump1[20][200005];
void init(int N, vector<int> H) {
	n=N;
	v=H;
	a.resize(n,-1);
	b.resize(n,-1);
	pl.resize(n+1);
	vector<int> st;
	for(int i=0;i<n;i++){
		pl[v[i]]=i;
		while(st.size()&&v[st.back()]<v[i]){
			st.pop_back();
		}
		a[i]=(st.size()?st.back():-1);
		st.push_back(i);
	}
	st.clear();
	for(int i=n-1;i>=0;i--){
		while(st.size()&&v[st.back()]<v[i]){
			st.pop_back();
		}
		b[i]=(st.size()?st.back():-1);
		st.push_back(i);
	}
	for(int i=0;i<n;i++){
		if(a[i]==-1)swap(a[i],b[i]);
		else if(b[i]==-1)continue;
		else {
			if(v[a[i]]<v[b[i]]){
				swap(a[i],b[i]);
			}
		}
	}
	for(int j=n;j>=1;j--){
		int i=pl[j];
		int now=a[i];
		jump[0][i]=now;
		for(int k=1;k<20;k++){
			if(now==-1){
				jump[k][i]=-1;
				continue;
			}
			else{
				now=jump[k][i]=jump[k-1][now];
			}
		}
		now=b[i];
		jump1[0][i]=now;
		for(int k=1;k<20;k++){
			if(now==-1){
				jump1[k][i]=-1;
				continue;
			}
			else{
				now=jump1[k][i]=jump1[k-1][now];
			}
		}
	}
}
int f(int A, int C) {
    int ans=0;
	int now=A;
	for(int k=19;k>=0;k--){
		int tmp=jump[k][now];
		if(tmp!=-1&&v[tmp]<=v[C]){
			ans+=(1<<k);
			now=tmp;
		}
	}
	for(int k=19;k>=0;k--){
		int tmp=jump1[k][now];
		if(tmp!=-1&&v[tmp]<=v[C]){
			ans+=(1<<k);
			now=tmp;
		}
	}
	if(now!=C)ans=1e9;
	return ans;
}
int minimum_jumps(int A, int B, int C, int D) {
    int ans=1e9;
	/*for(int i=A;i<=B;i++){
		for(int j=C;j<=D;j++){
			ans=min(ans,f(i,j));
		}
	}*/
	int tmp=-1;
	for(int i=1;i<=n;i++){
		if(pl[i]>=A&&pl[i]<=B){
			tmp=pl[i];
		}
		if(tmp!=-1&&pl[i]>=C&&pl[i]<=D){
			ans=min(ans,f(tmp,pl[i]));
		}
	}
	if(ans==1e9)ans=-1;
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 4 ms 31316 KB Output is correct
3 Execution timed out 4027 ms 36004 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31060 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 3 ms 31064 KB Output is correct
5 Correct 76 ms 35364 KB Output is correct
6 Correct 118 ms 36440 KB Output is correct
7 Correct 39 ms 33624 KB Output is correct
8 Correct 106 ms 36296 KB Output is correct
9 Correct 10 ms 31864 KB Output is correct
10 Correct 112 ms 36504 KB Output is correct
11 Correct 54 ms 37212 KB Output is correct
12 Correct 63 ms 37072 KB Output is correct
13 Correct 49 ms 36908 KB Output is correct
14 Correct 84 ms 36452 KB Output is correct
15 Correct 52 ms 36924 KB Output is correct
16 Correct 47 ms 37288 KB Output is correct
17 Correct 50 ms 37164 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 31224 KB Output is correct
20 Correct 4 ms 31064 KB Output is correct
21 Correct 4 ms 31072 KB Output is correct
22 Incorrect 4 ms 31064 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 4 ms 31208 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Execution timed out 4035 ms 33556 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 4 ms 31208 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Execution timed out 4035 ms 33556 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 4 ms 31316 KB Output is correct
3 Execution timed out 4027 ms 36004 KB Time limit exceeded
4 Halted 0 ms 0 KB -