oj.uz

Submission #799175

# Submission time Handle Problem Language Result Execution time Memory
799175 2023-07-31T10:31:16 Z lollipop Sky Walking (IOI19_walk) C++17
10 / 100
 398 ms 579340 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 = 2e6 + 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 130 ms 282060 KB Output is correct
2 Correct 120 ms 282056 KB Output is correct
3 Correct 125 ms 282020 KB Output is correct
4 Correct 116 ms 282024 KB Output is correct
5 Correct 117 ms 282188 KB Output is correct
6 Correct 116 ms 282248 KB Output is correct
7 Correct 119 ms 282264 KB Output is correct
8 Correct 116 ms 282184 KB Output is correct
9 Correct 117 ms 282152 KB Output is correct
10 Correct 118 ms 282348 KB Output is correct
11 Correct 116 ms 282072 KB Output is correct
12 Correct 120 ms 282040 KB Output is correct
13 Correct 115 ms 282124 KB Output is correct
14 Correct 115 ms 282048 KB Output is correct
15 Correct 115 ms 282052 KB Output is correct
16 Correct 116 ms 282056 KB Output is correct
17 Correct 115 ms 282324 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 282080 KB Output is correct
2 Correct 116 ms 282024 KB Output is correct
3 Runtime error 398 ms 579340 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 230 ms 302604 KB Output is correct
2 Runtime error 349 ms 578312 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 230 ms 302604 KB Output is correct
2 Runtime error 349 ms 578312 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 130 ms 282060 KB Output is correct
2 Correct 120 ms 282056 KB Output is correct
3 Correct 125 ms 282020 KB Output is correct
4 Correct 116 ms 282024 KB Output is correct
5 Correct 117 ms 282188 KB Output is correct
6 Correct 116 ms 282248 KB Output is correct
7 Correct 119 ms 282264 KB Output is correct
8 Correct 116 ms 282184 KB Output is correct
9 Correct 117 ms 282152 KB Output is correct
10 Correct 118 ms 282348 KB Output is correct
11 Correct 116 ms 282072 KB Output is correct
12 Correct 120 ms 282040 KB Output is correct
13 Correct 115 ms 282124 KB Output is correct
14 Correct 115 ms 282048 KB Output is correct
15 Correct 115 ms 282052 KB Output is correct
16 Correct 116 ms 282056 KB Output is correct
17 Correct 115 ms 282324 KB Output is correct
18 Correct 116 ms 282080 KB Output is correct
19 Correct 116 ms 282024 KB Output is correct
20 Runtime error 398 ms 579340 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -