Submission #532952

#TimeUsernameProblemLanguageResultExecution timeMemory
532952vinnipuh01Rainforest Jumps (APIO21_jumps)C++17
60 / 100
4081 ms102900 KiB
//#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; int a[ 200001 ], l[ 200001 ], r[ 200001 ], sum = 0; vector <int> v[ 200001 ], vv; vector <pair<int, int> > v1; bool ok; 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 } ); } 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; } 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 (stderr)

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