oj.uz

Submission #799176

# Submission time Handle Problem Language Result Execution time Memory
799176 2023-07-31T10:32:09 Z lollipop Sky Walking (IOI19_walk) C++17
10 / 100
 421 ms 834404 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 704720 KB Output is correct
2 Correct 287 ms 704792 KB Output is correct
3 Correct 282 ms 704732 KB Output is correct
4 Correct 284 ms 704796 KB Output is correct
5 Correct 308 ms 704916 KB Output is correct
6 Correct 286 ms 704868 KB Output is correct
7 Correct 290 ms 704868 KB Output is correct
8 Correct 282 ms 704836 KB Output is correct
9 Correct 303 ms 704748 KB Output is correct
10 Correct 292 ms 705036 KB Output is correct
11 Correct 290 ms 704760 KB Output is correct
12 Correct 281 ms 704836 KB Output is correct
13 Correct 292 ms 704776 KB Output is correct
14 Correct 282 ms 704812 KB Output is correct
15 Correct 283 ms 704976 KB Output is correct
16 Correct 338 ms 704740 KB Output is correct
17 Correct 298 ms 705036 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 704748 KB Output is correct
2 Correct 279 ms 704688 KB Output is correct
3 Runtime error 404 ms 834404 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 725392 KB Output is correct
2 Runtime error 357 ms 833968 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 725392 KB Output is correct
2 Runtime error 357 ms 833968 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 704720 KB Output is correct
2 Correct 287 ms 704792 KB Output is correct
3 Correct 282 ms 704732 KB Output is correct
4 Correct 284 ms 704796 KB Output is correct
5 Correct 308 ms 704916 KB Output is correct
6 Correct 286 ms 704868 KB Output is correct
7 Correct 290 ms 704868 KB Output is correct
8 Correct 282 ms 704836 KB Output is correct
9 Correct 303 ms 704748 KB Output is correct
10 Correct 292 ms 705036 KB Output is correct
11 Correct 290 ms 704760 KB Output is correct
12 Correct 281 ms 704836 KB Output is correct
13 Correct 292 ms 704776 KB Output is correct
14 Correct 282 ms 704812 KB Output is correct
15 Correct 283 ms 704976 KB Output is correct
16 Correct 338 ms 704740 KB Output is correct
17 Correct 298 ms 705036 KB Output is correct
18 Correct 277 ms 704748 KB Output is correct
19 Correct 279 ms 704688 KB Output is correct
20 Runtime error 404 ms 834404 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -