Submission #799176

#TimeUsernameProblemLanguageResultExecution timeMemory
799176lollipopSky Walking (IOI19_walk)C++17
10 / 100
421 ms834404 KiB
#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() ){
      |     ^~~
#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...