oj.uz

Submission #792245

# Submission time Handle Problem Language Result Execution time Memory
792245 2023-07-24T20:53:37 Z lollipop Ancient Books (IOI17_books) C++17
100 / 100
 1190 ms 253552 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47300 KB Output is correct
2 Correct 21 ms 47304 KB Output is correct
3 Correct 21 ms 47292 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 20 ms 47260 KB Output is correct
6 Correct 25 ms 47292 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47204 KB Output is correct
9 Correct 20 ms 47252 KB Output is correct
10 Correct 23 ms 47204 KB Output is correct
11 Correct 21 ms 47220 KB Output is correct
12 Correct 25 ms 47172 KB Output is correct
13 Correct 20 ms 47188 KB Output is correct
14 Correct 21 ms 47232 KB Output is correct
15 Correct 22 ms 47272 KB Output is correct
16 Correct 21 ms 47224 KB Output is correct
17 Correct 23 ms 47268 KB Output is correct
18 Correct 20 ms 47188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47300 KB Output is correct
2 Correct 21 ms 47304 KB Output is correct
3 Correct 21 ms 47292 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 20 ms 47260 KB Output is correct
6 Correct 25 ms 47292 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47204 KB Output is correct
9 Correct 20 ms 47252 KB Output is correct
10 Correct 23 ms 47204 KB Output is correct
11 Correct 21 ms 47220 KB Output is correct
12 Correct 25 ms 47172 KB Output is correct
13 Correct 20 ms 47188 KB Output is correct
14 Correct 21 ms 47232 KB Output is correct
15 Correct 22 ms 47272 KB Output is correct
16 Correct 21 ms 47224 KB Output is correct
17 Correct 23 ms 47268 KB Output is correct
18 Correct 20 ms 47188 KB Output is correct
19 Correct 22 ms 47428 KB Output is correct
20 Correct 21 ms 47300 KB Output is correct
21 Correct 21 ms 47440 KB Output is correct
22 Correct 22 ms 47444 KB Output is correct
23 Correct 22 ms 47496 KB Output is correct
24 Correct 22 ms 47392 KB Output is correct
25 Correct 22 ms 47372 KB Output is correct
26 Correct 22 ms 47340 KB Output is correct
27 Correct 21 ms 47392 KB Output is correct
28 Correct 23 ms 47428 KB Output is correct
29 Correct 22 ms 47488 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47300 KB Output is correct
2 Correct 21 ms 47304 KB Output is correct
3 Correct 21 ms 47292 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 20 ms 47260 KB Output is correct
6 Correct 25 ms 47292 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47204 KB Output is correct
9 Correct 20 ms 47252 KB Output is correct
10 Correct 23 ms 47204 KB Output is correct
11 Correct 21 ms 47220 KB Output is correct
12 Correct 25 ms 47172 KB Output is correct
13 Correct 20 ms 47188 KB Output is correct
14 Correct 21 ms 47232 KB Output is correct
15 Correct 22 ms 47272 KB Output is correct
16 Correct 21 ms 47224 KB Output is correct
17 Correct 23 ms 47268 KB Output is correct
18 Correct 20 ms 47188 KB Output is correct
19 Correct 22 ms 47428 KB Output is correct
20 Correct 21 ms 47300 KB Output is correct
21 Correct 21 ms 47440 KB Output is correct
22 Correct 22 ms 47444 KB Output is correct
23 Correct 22 ms 47496 KB Output is correct
24 Correct 22 ms 47392 KB Output is correct
25 Correct 22 ms 47372 KB Output is correct
26 Correct 22 ms 47340 KB Output is correct
27 Correct 21 ms 47392 KB Output is correct
28 Correct 23 ms 47428 KB Output is correct
29 Correct 22 ms 47488 KB Output is correct
30 Correct 612 ms 163784 KB Output is correct
31 Correct 784 ms 175984 KB Output is correct
32 Correct 794 ms 246956 KB Output is correct
33 Correct 573 ms 227512 KB Output is correct
34 Correct 613 ms 227568 KB Output is correct
35 Correct 593 ms 225144 KB Output is correct
36 Correct 549 ms 201716 KB Output is correct
37 Correct 569 ms 189836 KB Output is correct
38 Correct 577 ms 188760 KB Output is correct
39 Correct 645 ms 188812 KB Output is correct
40 Correct 628 ms 190304 KB Output is correct
41 Correct 726 ms 186524 KB Output is correct
42 Correct 781 ms 198648 KB Output is correct
43 Correct 704 ms 230680 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47444 KB Output is correct
2 Correct 21 ms 47444 KB Output is correct
3 Correct 21 ms 47480 KB Output is correct
4 Correct 22 ms 47492 KB Output is correct
5 Correct 22 ms 47360 KB Output is correct
6 Correct 21 ms 47472 KB Output is correct
7 Correct 22 ms 47452 KB Output is correct
8 Correct 25 ms 47444 KB Output is correct
9 Correct 23 ms 47396 KB Output is correct
10 Correct 22 ms 47400 KB Output is correct
11 Correct 24 ms 47352 KB Output is correct
12 Correct 22 ms 47436 KB Output is correct
13 Correct 21 ms 47356 KB Output is correct
14 Correct 23 ms 47444 KB Output is correct
15 Correct 23 ms 47396 KB Output is correct
16 Correct 22 ms 47400 KB Output is correct
17 Correct 22 ms 47432 KB Output is correct
18 Correct 22 ms 47420 KB Output is correct
19 Correct 22 ms 47360 KB Output is correct
20 Correct 23 ms 47412 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47300 KB Output is correct
2 Correct 21 ms 47304 KB Output is correct
3 Correct 21 ms 47292 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 20 ms 47260 KB Output is correct
6 Correct 25 ms 47292 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47204 KB Output is correct
9 Correct 20 ms 47252 KB Output is correct
10 Correct 23 ms 47204 KB Output is correct
11 Correct 21 ms 47220 KB Output is correct
12 Correct 25 ms 47172 KB Output is correct
13 Correct 20 ms 47188 KB Output is correct
14 Correct 21 ms 47232 KB Output is correct
15 Correct 22 ms 47272 KB Output is correct
16 Correct 21 ms 47224 KB Output is correct
17 Correct 23 ms 47268 KB Output is correct
18 Correct 20 ms 47188 KB Output is correct
19 Correct 22 ms 47428 KB Output is correct
20 Correct 21 ms 47300 KB Output is correct
21 Correct 21 ms 47440 KB Output is correct
22 Correct 22 ms 47444 KB Output is correct
23 Correct 22 ms 47496 KB Output is correct
24 Correct 22 ms 47392 KB Output is correct
25 Correct 22 ms 47372 KB Output is correct
26 Correct 22 ms 47340 KB Output is correct
27 Correct 21 ms 47392 KB Output is correct
28 Correct 23 ms 47428 KB Output is correct
29 Correct 22 ms 47488 KB Output is correct
30 Correct 612 ms 163784 KB Output is correct
31 Correct 784 ms 175984 KB Output is correct
32 Correct 794 ms 246956 KB Output is correct
33 Correct 573 ms 227512 KB Output is correct
34 Correct 613 ms 227568 KB Output is correct
35 Correct 593 ms 225144 KB Output is correct
36 Correct 549 ms 201716 KB Output is correct
37 Correct 569 ms 189836 KB Output is correct
38 Correct 577 ms 188760 KB Output is correct
39 Correct 645 ms 188812 KB Output is correct
40 Correct 628 ms 190304 KB Output is correct
41 Correct 726 ms 186524 KB Output is correct
42 Correct 781 ms 198648 KB Output is correct
43 Correct 704 ms 230680 KB Output is correct
44 Correct 21 ms 47444 KB Output is correct
45 Correct 21 ms 47444 KB Output is correct
46 Correct 21 ms 47480 KB Output is correct
47 Correct 22 ms 47492 KB Output is correct
48 Correct 22 ms 47360 KB Output is correct
49 Correct 21 ms 47472 KB Output is correct
50 Correct 22 ms 47452 KB Output is correct
51 Correct 25 ms 47444 KB Output is correct
52 Correct 23 ms 47396 KB Output is correct
53 Correct 22 ms 47400 KB Output is correct
54 Correct 24 ms 47352 KB Output is correct
55 Correct 22 ms 47436 KB Output is correct
56 Correct 21 ms 47356 KB Output is correct
57 Correct 23 ms 47444 KB Output is correct
58 Correct 23 ms 47396 KB Output is correct
59 Correct 22 ms 47400 KB Output is correct
60 Correct 22 ms 47432 KB Output is correct
61 Correct 22 ms 47420 KB Output is correct
62 Correct 22 ms 47360 KB Output is correct
63 Correct 23 ms 47412 KB Output is correct
64 Correct 921 ms 240088 KB Output is correct
65 Correct 866 ms 243592 KB Output is correct
66 Correct 942 ms 196752 KB Output is correct
67 Correct 912 ms 195844 KB Output is correct
68 Correct 103 ms 63468 KB Output is correct
69 Correct 99 ms 62648 KB Output is correct
70 Correct 89 ms 63876 KB Output is correct
71 Correct 102 ms 67112 KB Output is correct
72 Correct 109 ms 69804 KB Output is correct
73 Correct 107 ms 62768 KB Output is correct
74 Correct 634 ms 234312 KB Output is correct
75 Correct 657 ms 234400 KB Output is correct
76 Correct 704 ms 236804 KB Output is correct
77 Correct 727 ms 237344 KB Output is correct
78 Correct 932 ms 231520 KB Output is correct
79 Correct 958 ms 230744 KB Output is correct
80 Correct 760 ms 253552 KB Output is correct
81 Correct 1190 ms 225188 KB Output is correct
82 Correct 1170 ms 225568 KB Output is correct
83 Correct 920 ms 215016 KB Output is correct
84 Correct 943 ms 210696 KB Output is correct
85 Correct 855 ms 201912 KB Output is correct
86 Correct 873 ms 197584 KB Output is correct
87 Correct 916 ms 244004 KB Output is correct
88 Correct 934 ms 235276 KB Output is correct
89 Correct 917 ms 219816 KB Output is correct
90 Correct 843 ms 195892 KB Output is correct
91 Correct 876 ms 195292 KB Output is correct
92 Correct 882 ms 195552 KB Output is correct