Submission #484177

#	Time	Username	Problem	Language	Result	Execution time	Memory
484177		vinnipuh01	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4013 ms	35560 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
#include <vector>

using namespace std;
int n;
int a[ 200001 ];
vector <int> v[ 200001 ], vv;

bool ok;

void init(int N, vector<int> H) {
	n = N;
	for ( int i = 0 ; i < H.size(); i ++ )
		a[ i + 1 ] = H[ i ];
	for ( int i = 1; i <= n; i ++ ) {
		while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
			vv.pop_back();
		}
		if ( vv.size() ) {
			v[ i ].push_back( vv.back() );
		}
		vv.push_back( i );
	}
	vv.clear();
	for ( int i = n; i >= 1; i -- ) {
		while ( vv.size() && a[ vv.back() ] < a[ i ] ) {
			vv.pop_back();
		}
		if ( vv.size() )
			v[ i ].push_back( vv.back() );
		vv.push_back( i );
	}
	for ( int i = n; i > 1; i -- ) {
		if ( a[ i ] <= a[ i - 1 ] )
			ok = 1;
	}
}

const long long oo = 1e18;
long long mx, mn;
int c, f;
map <int, long long> d;
map <int, bool> used;
queue <int> q;

long long int bfs() {
	mx = oo;
	while ( q.size() ) {
		int g = q.front();
		q.pop();
		for ( auto to : v[ g ] ) {
			if ( !used[ to ] || d[ to ] > d[ g ] + 1 ) {
				d[ to ] = d[ g ] + 1;
				q.push( to );
				if ( to >= c && to <= f ) {
					mx = min( d[ g ] + 1, mx );
				}
				used[ to ] = 1;
			}
		}
	}
	while( q.size() )
		q.pop();
	return mx;
}

int minimum_jumps(int A, int B, int C, int D) {
	A ++;
	B ++;
	C ++;
	D ++;
	if ( !ok ) {
		if ( C > B )
			return C - B;
		else
			return A - D;
	}
	d.clear();
	used.clear();
	c = C;
	f = D;
	mn = oo;
	for ( int i = A; i <= B; i ++ ) {
		q.push( i );
		used[ i ] = 1;
	}
	mn = bfs(  );
	if ( mn == oo )
		return -1;
  return mn;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for ( int i = 0 ; i < H.size(); i ++ )
      |                    ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19