Submission #792245

#	Time	Username	Problem	Language	Result	Execution time	Memory
792245		lollipop	Ancient Books (IOI17_books)	C++17	100 / 100	1190 ms	253552 KiB

books

#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 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 N = 2e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "books.h"

int pos[ N ] , been[ N ] , s , tt = 0 ;
vector < int > v[ N ] ; 
vector < int > vu ; 
ll get( int node ){
      if( node == s ) tt = 1 ; 
	been[ node ] = 1 ;
	vu.pb( node ) ; 
	ll cur = 0 ; 
	for( auto x : v[ node ] ){
//	      cout << node << " " << x << endl ;
		cur = cur + abs( x - node ) ;
		if( been[ x ] == 0 ) cur += get( x ) ; 
	}
	return cur ;
}
vector < vector < int > > vvv ;
int mxx[ N ] , mnn[ N ] ;
int roca_mtvare_varskvlavebs_naxavs = 0 ; 
map < int , int > mtvare ; 
long long minimum_walk(std::vector<int> p, int S){
       s = S ; 
	 int n = p.size() ;
	 ll ans = 0 ;
	 FOR( i , n ){
		v[ i ].pb( p[ i ] ) ;  
	 } 
	 set < int > se ;
	 pair < int , int > pp ; 
	 FOR( i , n ){
	 	if( been[ i ] == 1 ) continue ;
	 	tt = 0 ; 
	 	vu.clear() ; 
	 	ans += get( i ) ; 	 	
	 	sort( vu.begin() , vu.end() ) ; 
	 	int l = vu[ 0 ] ; 
	 	int r = vu[ vu.size() - 1 ] ;
	 //	cout << l << " " << r << endl ; 
	 	 if( tt == 1 ){
	 	      pp = { l , r } ; 
	 	 }
	 	 else{
	 	   	for( auto x : vu ) mtvare[ x ] = vvv.size() , se.insert( x ) ;  
	 	   	mxx[ vvv.size() ] = vu[ vu.size() - 1 ] ; 
	 	   	mnn[ vvv.size() ] = vu[ 0 ] ;  
	 	   	vvv.pb( vu ) ; 
	 	   	roca_mtvare_varskvlavebs_naxavs ++ ; 
		 }
	 }
	 //cout << roca_mtvare_varskvlavebs_naxavs << endl ;
	 //cout << ans << endl ; 
	 int mx = 0 ; 
	 int lst = n - 1 ; 
	 while( true ){
	       int p ; 
	       if( se.size() == 0 ) break ; 
	       p = *(--se.end() ) ;
	       if( p <= pp.s ) break ; 
	       if( vvv[ mtvare[ p ] ].size() == 1 && p == lst ){
	             lst -- ; 
	             se.erase( --se.end() ) ; 
	       } else break ; 
	 }
	 int ff = 0 ;
	 while( true ){
	       int p ; 
	       if( se.size() == 0 ) break ; 
	       p = *se.begin() ; 
	       if( p >= pp.f ) break ; 
	       if( vvv[ mtvare[ p ] ].size() == 1 && p == ff ){
	             ff ++ ; se.erase( se.begin() ) ; 
	       }
	       else break ;
	 }
//	 cout << ans << endl ; 
	 int l = pp.f , r = pp.s ; 
	 int titu = 0 ; 
	 while( true ){
	 	if( se.size() == 0 ) break ;
	 	int left = - INT_MAX + 10 * N , right = INT_MAX - 10 * N ;
	 	if( *se.begin() < l ) left = *( -- se.lower_bound( l ) ) ;
	 	if( *(--se.end() ) > l ) right = *se.lower_bound( l ) ;
        if( right < r || left == -INT_MAX + 10 * N ){
			int xx = 0 ;
			if( right > r ) xx = 2 ; 
	 	    ans = ans + xx ; 
	 	    int mn = INT_MAX , mx = 0 ; 
			for( auto x : vvv[ mtvare[ right ] ] ){
				se.erase( se.find( x ) ) ;
				mn = min( mn , x ) ;
				mx = max( mx , x ) ; 
			} 	
			l = min( mn , l ) ;
			r = max( mx , r ) ;
			continue ; 			
		}	 	
		if( titu == -1 || right == INT_MAX - 10 * N ){
			int xx = 0 ;
			if( right > r ) xx = 2 ; 
	 	    ans = ans + xx ; 
	 	    int mn = INT_MAX , mx = 0 ; 
			for( auto x : vvv[ mtvare[ left ] ] ){
				se.erase( se.find( x ) ) ;
				mn = min( mn , x ) ;
				mx = max( mx , x ) ; 
			} 	
			l = min( mn , l ) ;
			r = max( mx , r ) ;
			continue ; 			
		}
		int z = r ;
		while( true ){
			if( *( --se.end() ) == z ){
				titu = -1 ; break ; 
			} 
			z = *se.upper_bound( z ) ;
			if( mnn[ mtvare[ z ] ] < l ){
				break ; 
			}
		}
		if( titu == -1 ) continue ; 
        int l1 = l , r1 = r ; 
		int cost = 0 ;
		z = r ; 
		while( true ){
			z = *se.upper_bound( z ) ;
			if( z > r1 ){
				cost += 2 ; 
			}
			r1 = max( r1 , mxx[ mtvare[ z ] ] ) ; 
			if( mnn[ mtvare[ z ] ] < l ){
				break ; 
			}			
		} 
		int cost2 = 0 ;
		l1 = l , r1 = r ; z = r ; 
		while( true ){
			z = *( -- se.lower_bound( z ) ) ;
			if( z < l1 ){
				cost2 += 2 ; 
			}
			l1 = min( l1 , mnn[ mtvare[ z ] ] ) ; 
			if( mxx[ mtvare[ z ] ] > r ){
				break ; 
			}			
		} 		
		set < int > su ;
		if( cost < cost2 ){
         l1 = l , r1 = r ; 
		z = r ; 
		while( true ){
			if( *( --se.end() ) == z ){
				titu = -1 ; break ; 
			} 
			z = *se.upper_bound( z ) ;
			su.insert( mtvare[ z ] ) ; 
			if( mnn[ mtvare[ z ] ] < l ){
				break ; 
			}			
		 } 			
		}
		else{
		l1 = l , r1 = r ; z = r ; 
		while( true ){
			z = *( -- se.lower_bound( z ) ) ;
            su.insert( mtvare[ z ] ) ;
			if( mxx[ mtvare[ z ] ] > r ){
				break ; 
			}			
		  }			
		}
		ans += min( cost , cost2 ) ;
		for( auto x : su ){
			l = min( l , mnn[ x ] ) ; 
			r = max( r , mxx[ x ] ) ; 
			for( auto z : vvv[ x ] ) se.erase( se.find( z ) ) ; 
		} 		
		 		
	//	cout << " " << left << " " << right << "  " << ans << endl ; 
	 }
	 
	 return ans ;
}


//
//   int main() {
//   	int n, s;
//   	assert(2 == scanf("%d %d", &n, &s));
//   	vector<int> p((unsigned) n);
//   	for(int i = 0; i < n; i++)
//   		assert(1 == scanf("%d", &p[(unsigned) i]));
//   	long long res = minimum_walk(p, s);
//   	printf("%lld\n", res);
//   	return 0;
//   }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:84:7: warning: unused variable 'mx' [-Wunused-variable]
   84 |   int mx = 0 ;
      |       ^~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30