oj.uz

Submission #532986

# Submission time Handle Problem Language Result Execution time Memory
532986 2022-03-04T10:07:01 Z vinnipuh01 Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1256 ms 86260 KB 
#include "jump.h"
 
#include <bits/stdc++.h>
#include <vector>
 
using namespace std;
int n, par[ 200001 ][ 21 ], parr[ 200001 ][ 21 ], dist[ 200001 ][ 21 ], distt[ 200001 ][ 21 ];
int lg = 20, num;
int a[ 200001 ], l[ 200001 ][ 21 ], r[ 200001 ][ 21 ], sum = 0;
pair<int, int> t[ 800001 ];
vector <int> v[ 200001 ], vv;
vector <pair<int, int> > v1;

bool ok;

void build( int v, int tl, int tr ) {
	if ( tl == tr ) {
		t[ v ] = { a[ tl ], tl };
		return;
	}
	int mid = ( tl + tr ) / 2;
	build( v + v, tl, mid );
	build( v + v + 1, mid + 1, tr );
	t[ v ] = max( t[ v + v ], t[ v + v + 1 ] );
}

void gett( int v, int tl, int tr, int l, int r,int x ) {
	if ( tl > r || tr < l || t[ v ].first < x )
		return;
	if ( tl == tr ) {
		num = tl;
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett( v + v + 1, mid + 1, tr, l, r, x );
	if ( num )
		return;
	gett( v + v, tl, mid, l, r, x );
}

void get1( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		if ( t[ v ].first > a[ num ] )	
			num = t[ v ].second;
		return;
	}
	int mid = ( tl + tr ) / 2;
	get1( v + v, tl, mid, l, r );
	get1( v + v + 1, mid + 1, tr, l, r );
}

void init(int N, vector<int> H) {
	n = N;
	for ( int i = 0 ; i < H.size(); i ++ ) {
		a[ i + 1 ] = H[ i ];
		v1.push_back( { a[ i + 1 ], i + 1 } );
	}
	build( 1, 1, n );
	sort( v1.begin(), v1.end() );
	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 = 1; i <= n; i ++ ) {
		if ( v[ i ].size() == 1 ) {
			parr[ i ][ 0 ] = v[ i ].back();
			par[ i ][ 0 ] = i;
			dist[ i ][ 0 ] = 0;
			distt[ i ][ 0 ] = 1;
		}
		else if ( v[ i ].size() == 2 ) {
			if ( a[ v[ i ].back() ] > a[ v[ i ].front() ] ) {
				par[ i ][ 0 ] = v[ i ].back();
				parr[ i ][ 0 ] = v[ i ].front();
			}
			else {
				par[ i ][ 0 ] = v[ i ].front();
				parr[ i ][ 0 ] = v[ i ].back();
			}
			dist[  i][ 0 ] = distt[ i ][ 0 ] = 1;
		}
		else {
			par[ i ][ 0 ] = parr[ i ][ 0 ] = i;
			dist[ i ][ 0 ] = distt[ i ][ 0 ] = 0;
		}
	}
	for ( int i = v1.size() - 1; i >= 0; i -- ) {
		for ( int j = 1; j <= lg; j ++ ) {
			par[ v1[ i ].second ][ j ] = par[ par[ v1[ i ].second ][ j - 1 ]][ j - 1 ];
			dist[ v1[ i ].second ][ j ] = dist[ par[ v1[ i ].second ][ j - 1 ] ][ j - 1 ] + dist[ v1[ i ].second ][ j - 1 ];
			parr[ v1[ i ].second ][ j ] = parr[ parr[ v1[ i ].second ][ j - 1 ] ][ j - 1 ];
			distt[ v1[ i ].second ][ j ] = distt[ parr[ v1[ i ].second ][ j - 1 ] ][ j - 1 ] + distt[ v1[ i ].second ][ j - 1 ];
		}
	}
	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;
}

pair<int,int> lca( int aa, int b ) {
	int sum = 0;
	if ( aa == b )
		return { aa, 0 };
	for ( int i = lg; i >= 0; i -- ) {
		if ( a[ par[ aa ][ i ] ] <= a[ b ] ) {
			sum += dist[ aa ][ i ];
			aa = par[ aa ][ i ];
		}
	}
	return { aa, sum };
}

pair<int,int> lca1( int aa, int b ) {
	if ( aa == b )
		return { aa, 0 };
	int sum = 0;
	for ( int i = lg; i >= 0; i -- ) {
		if ( a[ parr[ aa ][ i ] ] < a[ b ] ) {
			sum += distt[ aa ][ i ];
			aa = parr[ aa ][ i ];
		}
	}
	return { parr[ aa ][ 0 ], sum + distt[ aa ][ 0 ] };
}

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;
	}
	if ( A == B && C == D ) {
		pair<int, int> p;
		p = lca( A, C );
		sum = p.second;
		p = lca1( p.first, C );
		if ( p.first == C )
			return sum + p.second;
		return -1;
	}
	get1( 1, 1, n, C, D );
	C = D = num;
	if ( C == D ) {
		num = 0;
		gett( 1, 1, n, A, B, a[ C ] );
		if ( !num )
			num = A;
		else
			num ++;
		if ( num == B + 1 )
			return -1;
		sum = num;
		num = 0;
		get1( 1, 1, n, sum, B );
		A = num;
		pair<int, int> p;
		p = lca( A, C );
		sum = p.second;
		p = lca1( p.first, C );
		if ( p.first == C )
			return sum + p.second;
		return -1;
	}
	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;
}


//int main () {
//	int n;
//	cin >> n;
//	int a;
//	vector <int> v;
//	v.clear();
//	for ( int i = 1; i <= n; i ++ )
//		cin >> a, v.push_back( a );
//	init( n, v );
//	int m, a, b, c, d;
//	cin >> m;
//	while ( m -- ) {
//		cin >> a >> b >> c >> d;
//		
//	}
//}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 166 ms 70116 KB Output is correct
4 Correct 776 ms 85812 KB Output is correct
5 Correct 812 ms 45620 KB Output is correct
6 Correct 954 ms 85768 KB Output is correct
7 Correct 799 ms 61872 KB Output is correct
8 Correct 951 ms 85704 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 3 ms 4936 KB Output is correct
4 Correct 320 ms 41700 KB Output is correct
5 Correct 1152 ms 85008 KB Output is correct
6 Correct 769 ms 18580 KB Output is correct
7 Correct 1027 ms 85092 KB Output is correct
8 Correct 508 ms 33204 KB Output is correct
9 Correct 1012 ms 85024 KB Output is correct
10 Correct 820 ms 85720 KB Output is correct
11 Correct 647 ms 86260 KB Output is correct
12 Correct 976 ms 85604 KB Output is correct
13 Correct 1006 ms 84972 KB Output is correct
14 Correct 1133 ms 85424 KB Output is correct
15 Correct 1126 ms 85820 KB Output is correct
16 Correct 747 ms 85816 KB Output is correct
17 Correct 3 ms 4916 KB Output is correct
18 Correct 3 ms 4936 KB Output is correct
19 Correct 4 ms 4932 KB Output is correct
20 Correct 5 ms 5064 KB Output is correct
21 Correct 6 ms 5064 KB Output is correct
22 Correct 5 ms 5064 KB Output is correct
23 Correct 4 ms 5108 KB Output is correct
24 Correct 5 ms 5064 KB Output is correct
25 Correct 3 ms 5064 KB Output is correct
26 Correct 4 ms 5248 KB Output is correct
27 Correct 24 ms 5704 KB Output is correct
28 Correct 28 ms 5704 KB Output is correct
29 Correct 24 ms 5704 KB Output is correct
30 Correct 21 ms 5704 KB Output is correct
31 Correct 23 ms 5824 KB Output is correct
32 Correct 3 ms 4936 KB Output is correct
33 Correct 135 ms 51016 KB Output is correct
34 Correct 227 ms 84912 KB Output is correct
35 Correct 144 ms 85696 KB Output is correct
36 Correct 203 ms 84916 KB Output is correct
37 Correct 200 ms 85344 KB Output is correct
38 Correct 147 ms 85784 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 3 ms 4936 KB Output is correct
4 Correct 320 ms 41700 KB Output is correct
5 Correct 1152 ms 85008 KB Output is correct
6 Correct 769 ms 18580 KB Output is correct
7 Correct 1027 ms 85092 KB Output is correct
8 Correct 508 ms 33204 KB Output is correct
9 Correct 1012 ms 85024 KB Output is correct
10 Correct 820 ms 85720 KB Output is correct
11 Correct 647 ms 86260 KB Output is correct
12 Correct 976 ms 85604 KB Output is correct
13 Correct 1006 ms 84972 KB Output is correct
14 Correct 1133 ms 85424 KB Output is correct
15 Correct 1126 ms 85820 KB Output is correct
16 Correct 747 ms 85816 KB Output is correct
17 Correct 3 ms 4916 KB Output is correct
18 Correct 3 ms 4936 KB Output is correct
19 Correct 4 ms 4932 KB Output is correct
20 Correct 5 ms 5064 KB Output is correct
21 Correct 6 ms 5064 KB Output is correct
22 Correct 5 ms 5064 KB Output is correct
23 Correct 4 ms 5108 KB Output is correct
24 Correct 5 ms 5064 KB Output is correct
25 Correct 3 ms 5064 KB Output is correct
26 Correct 4 ms 5248 KB Output is correct
27 Correct 24 ms 5704 KB Output is correct
28 Correct 28 ms 5704 KB Output is correct
29 Correct 24 ms 5704 KB Output is correct
30 Correct 21 ms 5704 KB Output is correct
31 Correct 23 ms 5824 KB Output is correct
32 Correct 3 ms 4936 KB Output is correct
33 Correct 135 ms 51016 KB Output is correct
34 Correct 227 ms 84912 KB Output is correct
35 Correct 144 ms 85696 KB Output is correct
36 Correct 203 ms 84916 KB Output is correct
37 Correct 200 ms 85344 KB Output is correct
38 Correct 147 ms 85784 KB Output is correct
39 Correct 3 ms 4936 KB Output is correct
40 Correct 3 ms 4936 KB Output is correct
41 Correct 3 ms 5004 KB Output is correct
42 Correct 331 ms 41800 KB Output is correct
43 Correct 1113 ms 84968 KB Output is correct
44 Correct 631 ms 18492 KB Output is correct
45 Correct 1119 ms 85036 KB Output is correct
46 Correct 653 ms 33132 KB Output is correct
47 Correct 1256 ms 84988 KB Output is correct
48 Correct 922 ms 85744 KB Output is correct
49 Correct 801 ms 86064 KB Output is correct
50 Correct 1193 ms 85680 KB Output is correct
51 Correct 848 ms 85028 KB Output is correct
52 Correct 1208 ms 85420 KB Output is correct
53 Correct 983 ms 85808 KB Output is correct
54 Correct 1101 ms 85740 KB Output is correct
55 Correct 3 ms 4936 KB Output is correct
56 Incorrect 270 ms 84828 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 166 ms 70116 KB Output is correct
4 Correct 776 ms 85812 KB Output is correct
5 Correct 812 ms 45620 KB Output is correct
6 Correct 954 ms 85768 KB Output is correct
7 Correct 799 ms 61872 KB Output is correct
8 Correct 951 ms 85704 KB Output is correct
9 Incorrect 3 ms 4936 KB Output isn't correct
10 Halted 0 ms 0 KB -