oj.uz

Submission #434121

# Submission time Handle Problem Language Result Execution time Memory
434121 2021-06-20T15:19:25 Z dqhungdl Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1538 ms 66936 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
const int MAX=2e5+5;
int Lg[MAX],J[MAX][20],JR[MAX][20];
ii f[MAX][20];

ii query(int l,int r) {
	if(l>r)
		return ii(-1,-1);
	int k=Lg[r-l+1];
	return max(f[l][k],f[r-(1<<k)+1][k]);
}

void init(int N, std::vector<int> H) {
	// Init log
	for(int i=1;i<=N;i++)
		Lg[i]=log2(i);
	// Init RMQ
	for(int i=0;i<N;i++)
		f[i][0]=ii(H[i],i);
	for(int k=1;(1<<k)<=N;k++)
		for(int i=0;i+(1<<k)-1<N;i++)
			f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	vector<int> L(N),R(N);
	// Init left
	for(int i=0; i<N;i++) {
		int tmp=i-1;
		while(tmp>=0&&H[tmp]<=H[i])
			tmp=L[tmp];
		L[i]=tmp;
	}
	// Init right
	for(int i=N-1; i>=0;i--) {
		int tmp=i+1;
		while(tmp<N&&H[tmp]<=H[i])
			tmp=R[tmp];
		R[i]=tmp;
	}
	// Init jumps RMQ
	for(int i=0;i<N;i++) {
		if(L[i]==-1&&R[i]==N)
			J[i][0]=-1;
		else if(L[i]==-1)
			J[i][0]=R[i];
		else if(R[i]==N)
			J[i][0]=L[i];
		else if(H[L[i]]>H[R[i]])
			J[i][0]=L[i];
		else
			J[i][0]=R[i];
	}
	for(int k=1;k<20;k++)
		for(int i=0;i<N;i++)
			if(J[i][k-1]==-1)
				J[i][k]=-1;
			else
				J[i][k]=J[J[i][k-1]][k-1];
	// Init jumps right RMQ
	for(int i=0;i<N;i++)
		JR[i][0]=R[i];
	for(int k=1;k<20;k++)
		for(int i=0;i<N;i++)
			if(JR[i][k-1]==N)
				JR[i][k]=N;
			else
				JR[i][k]=JR[JR[i][k-1]][k-1];
}

int minimum_jumps(int A, int B, int C, int D) {
	// Invalid cases
	ii maxBC=query(B+1,C-1),maxCD=query(C,D);
	if(maxBC.first>=maxCD.first)
		return -1;
	if(f[B][0].first>=maxCD.first)
		return -1;
	// Find the starting position
	int pos=B;
	for(int i=19;i>=0;i--) {
		if((1<<i)>pos-A+1||f[pos-(1<<i)+1][i].first>=maxCD.first)
			continue;
		pos=pos-(1<<i)+1;
	}
	pos=query(pos,B).second;
	// RMQ jumps
	int rs=0;
	for(int i=19;i>=0;i--) {
		if(J[pos][i]==-1||f[J[pos][i]][0]>=maxBC)
			continue;
		pos=J[pos][i];
		rs+=(1<<i);
	}
	// RMQ jumps right
	for(int i=19;i>=0;i--)
		if(JR[pos][i]<C) {
			rs+=(1<<i);
			pos=JR[pos][i];
		}
	return rs+1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 252 ms 53144 KB Output is correct
4 Correct 1474 ms 66736 KB Output is correct
5 Correct 1099 ms 33688 KB Output is correct
6 Correct 1467 ms 66752 KB Output is correct
7 Correct 1210 ms 45764 KB Output is correct
8 Correct 1538 ms 66716 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 151 ms 53744 KB Output is correct
6 Correct 207 ms 66752 KB Output is correct
7 Correct 87 ms 34240 KB Output is correct
8 Correct 198 ms 66740 KB Output is correct
9 Correct 14 ms 10288 KB Output is correct
10 Correct 194 ms 66752 KB Output is correct
11 Correct 203 ms 66752 KB Output is correct
12 Correct 185 ms 66936 KB Output is correct
13 Incorrect 194 ms 66916 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 274 ms 30604 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 274 ms 30604 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 252 ms 53144 KB Output is correct
4 Correct 1474 ms 66736 KB Output is correct
5 Correct 1099 ms 33688 KB Output is correct
6 Correct 1467 ms 66752 KB Output is correct
7 Correct 1210 ms 45764 KB Output is correct
8 Correct 1538 ms 66716 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Incorrect 3 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -