Submission #799176

#	Time	Username	Problem	Language	Result	Execution time	Memory
799176		lollipop	Sky Walking (IOI19_walk)	C++17	10 / 100	421 ms	834404 KiB

walk

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int NN = 5e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma[ NN ] , ma1 ;
//#include "walk.h"

vector < pair < int , int > > ve[ NN ] , v[ NN ] ;
set < int > se[ NN ] ;
ll been[ NN ] ; 
ll dij( int st , int fn , int cnt ){
	FOR( i , cnt ) been[ i ] = inf ;
	been[ st ] = 0 ;
	priority_queue < pair < ll , int > > qu ;
	qu.push( { 0 , st } ) ;
	while( true ){
      if( qu.size() == 0 ) break ;
	  pair < ll , int > p ;
	  p = qu.top() ; qu.pop() ;
	  p.f = abs( p.f ) ;
	  if( p.f > been[ p.s ] ) continue ;
	  for( auto x : v[ p.s ] ){
		ll lil = p.f ; lil += x.s ;
		 if( been[ x.f ] > lil ){
			been[ x.f ] = lil ;
			qu.push( { -been[ x.f ] , x.f } ) ;
		 }
	  }
	}
	if( been[ fn ] == inf ) return -1 ;
	return been[ fn ] ;
}

pair < int , int > node[ 4 * NN ] ;
int arr[ NN ] ;
void build( int v , int vl , int vr ){
	 if( vl == vr ){
		node[ v ] = { arr[ vl ] , vl } ;
		return ;
	 }
	 int vm = ( vl + vr ) / 2 ; 
	 build( v + v , vl , vm ) ;
	 build( v + v + 1 , vm + 1 , vr ) ;
	 node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ;
	 return ;
}
void update( int v , int vl , int vr , int pos , int val ){
	 if( vl == vr ){
		node[ v ].f = val ;
		return ;
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) update( v + v , vl , vm , pos , val ) ;
	 else update( v + v + 1 , vm + 1 , vr , pos , val ) ;
	 node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ;
	 return ; 
}
pair < int , int > get( int v , int vl , int vr , int l , int r ){
	 if( l > r ) return { -1 , -1 } ;
	 if( vl == l && vr == r ) return node[ v ] ;
	 int vm = ( vl + vr ) / 2 ;
	 pair < int , int > a , b ;
	 a = get( v + v , vl , vm , l , min( vm , r ) ) ; 
	 b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	 return max( a , b ) ;
}

ll min_distance(vector<signed> x,vector<signed> h,vector<signed> l,
                vector<signed> r,vector<signed> y, signed s, signed g){
    if( x.size() <= 50 && l.size() <= 50 ){
      FOR( i ,  l.size() ){
		int L = l[ i ] ; 
		int R = r[ i ] ;
		int H = y[ i ] ;
		int lst = L ;
		for( int j = L + 1 ; j <= R ; j ++ ){
           if( h[ j ] >= H ){
			ve[ lst ].pb( { j , H } ) ;
			ve[ j ].pb( { lst , H } ) ; 
			se[ j ].insert( H ) ;
			se[ lst ].insert( H ) ; 
			lst = j ;
		   }
		}
	  }
	}
	else{
      FOR( i , x.size() ){
		arr[ i + 1 ] = x[ i ] ;
	  }
      build( 1 , 1 , x.size() ) ;
      FOR( i ,  l.size() ){
		int L = l[ i ] ; 
		int R = r[ i ] ;
		int H = y[ i ] ;
		vector < int > vu ; 
		while( true ){
          pair < int , int > b ;
		  b = get( 1 , 1 , x.size() , L + 1 , R + 1 ) ;
		  if( b.f < H ) break ;
		  vu.pb( b.s - 1 ) ; 
		  update( 1 , 1 , x.size() , b.s , -1 ) ;
		}
		sort( vu.begin() , vu.end() ) ;
		FOR( i , vu.size() - 1 ){
			int lst = vu[ i ] ; int j = vu[ i + 1 ] ;
			ve[ lst ].pb( { j , H } ) ;
			ve[ j ].pb( { lst , H } ) ; 
			se[ j ].insert( H ) ;
			se[ lst ].insert( H ) ; 			
		}
		for( auto X : vu ){
			update( 1 , 1 , x.size() , X + 1 , x[ X ] ) ;
		}
	  }     

	}
	int cnt = 1 ;
	FOR( i , x.size() ){
      se[ i ].insert( 0 ) ;
	  int lst = -1 ;
	  for( auto x : se[ i ] ){
         ma[ i ][ x ] = cnt ; cnt ++ ;
		 if( lst == -1 ){
			lst = x ; continue ;
		 }
		 int df = x - lst ;
		 v[ ma[ i ][ x ] ].pb( { ma[ i ][ lst ] , df } ) ;
		 v[ ma[ i ][ lst ] ].pb( { ma[ i ][ x ] , df } ) ;
		 lst = x ;
	  }
	}
    FOR( i , x.size() ){
		for( auto z : ve[ i ] ){
			int a = ma[ i ][ z.s ] ;
			int b = ma[ z.f ][ z.s ] ;
			int df = abs( x[ i ] - x[ z.f ] ) ;
			v[ a ].pb( { b , df } ) ;
		}
	}
	int st = ma[ s ][ 0 ] ;
	int fn = ma[ g ][ 0 ] ;
	return dij( st , fn , cnt ) ;
}


// int main() {
// 	int n, m;
// 	cin >> n >> m ;
// 	vector<int> x(n), h(n);
// 	for (int i = 0; i < n; i++)
// 		cin >> x[ i ] >> h[ i ] ;
// 	vector<int> l(m), r(m), y(m);
// 	for (int i = 0; i < m; i++)
// 		cin >> l[ i ] >> r[ i ] >> y[ i ] ;
// 	int s, g;
// 	cin >> s >> g ; 
//     debug ;
// 	long long result = 10 ; //min_distance(x, h, l, r, y, s, g);

// 	printf("%lld\n", result);
// 	return 0;
// }

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   98 |       FOR( i ,  l.size() ){
      |            ~~~~~~~~~~~~~                 
walk.cpp:98:7: note: in expansion of macro 'FOR'
   98 |       FOR( i ,  l.size() ){
      |       ^~~
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  115 |       FOR( i , x.size() ){
      |            ~~~~~~~~~~~~                  
walk.cpp:115:7: note: in expansion of macro 'FOR'
  115 |       FOR( i , x.size() ){
      |       ^~~
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  119 |       FOR( i ,  l.size() ){
      |            ~~~~~~~~~~~~~                 
walk.cpp:119:7: note: in expansion of macro 'FOR'
  119 |       FOR( i ,  l.size() ){
      |       ^~~
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  132 |   FOR( i , vu.size() - 1 ){
      |        ~~~~~~~~~~~~~~~~~                 
walk.cpp:132:3: note: in expansion of macro 'FOR'
  132 |   FOR( i , vu.size() - 1 ){
      |   ^~~
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  146 |  FOR( i , x.size() ){
      |       ~~~~~~~~~~~~                       
walk.cpp:146:2: note: in expansion of macro 'FOR'
  146 |  FOR( i , x.size() ){
      |  ^~~
walk.cpp:13:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  160 |     FOR( i , x.size() ){
      |          ~~~~~~~~~~~~                    
walk.cpp:160:5: note: in expansion of macro 'FOR'
  160 |     FOR( i , x.size() ){
      |     ^~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43