oj.uz

Submission #792243

# Submission time Handle Problem Language Result Execution time Memory
792243 2023-07-24T20:32:33 Z lollipop Ancient Books (IOI17_books) C++17
50 / 100
 799 ms 246892 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 ; 
	 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 ) ;
       // cout << l << " " << r ;
        int cicabo = 0 ; 
        if( left != -INT_MAX + 10 * N ){
        	if( mxx[ mtvare[ left ] ] > left ) cicabo = -1 ; 
		}
		if( right != INT_MAX - 10 * N ){
			if( mnn[ mtvare[ right ] ] > left ) cicabo = -1 ; 
		}
	 	if( l - left + cicabo < right - r ){
	 	    ans = ans + 2 ; 
	 	    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 ) ;
		}
		else{
			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 ) ;			
		}	 	
	//	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 21 ms 47228 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Correct 23 ms 47268 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 21 ms 47188 KB Output is correct
6 Correct 21 ms 47188 KB Output is correct
7 Correct 21 ms 47272 KB Output is correct
8 Correct 20 ms 47188 KB Output is correct
9 Correct 22 ms 47304 KB Output is correct
10 Correct 20 ms 47252 KB Output is correct
11 Correct 21 ms 47304 KB Output is correct
12 Correct 21 ms 47192 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47284 KB Output is correct
15 Correct 21 ms 47188 KB Output is correct
16 Correct 21 ms 47292 KB Output is correct
17 Correct 22 ms 47296 KB Output is correct
18 Correct 21 ms 47196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47228 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Correct 23 ms 47268 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 21 ms 47188 KB Output is correct
6 Correct 21 ms 47188 KB Output is correct
7 Correct 21 ms 47272 KB Output is correct
8 Correct 20 ms 47188 KB Output is correct
9 Correct 22 ms 47304 KB Output is correct
10 Correct 20 ms 47252 KB Output is correct
11 Correct 21 ms 47304 KB Output is correct
12 Correct 21 ms 47192 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47284 KB Output is correct
15 Correct 21 ms 47188 KB Output is correct
16 Correct 21 ms 47292 KB Output is correct
17 Correct 22 ms 47296 KB Output is correct
18 Correct 21 ms 47196 KB Output is correct
19 Correct 21 ms 47316 KB Output is correct
20 Correct 21 ms 47424 KB Output is correct
21 Correct 23 ms 47504 KB Output is correct
22 Correct 22 ms 47464 KB Output is correct
23 Correct 22 ms 47444 KB Output is correct
24 Correct 24 ms 47376 KB Output is correct
25 Correct 22 ms 47352 KB Output is correct
26 Correct 23 ms 47432 KB Output is correct
27 Correct 26 ms 47316 KB Output is correct
28 Correct 23 ms 47340 KB Output is correct
29 Correct 22 ms 47440 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47228 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Correct 23 ms 47268 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 21 ms 47188 KB Output is correct
6 Correct 21 ms 47188 KB Output is correct
7 Correct 21 ms 47272 KB Output is correct
8 Correct 20 ms 47188 KB Output is correct
9 Correct 22 ms 47304 KB Output is correct
10 Correct 20 ms 47252 KB Output is correct
11 Correct 21 ms 47304 KB Output is correct
12 Correct 21 ms 47192 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47284 KB Output is correct
15 Correct 21 ms 47188 KB Output is correct
16 Correct 21 ms 47292 KB Output is correct
17 Correct 22 ms 47296 KB Output is correct
18 Correct 21 ms 47196 KB Output is correct
19 Correct 21 ms 47316 KB Output is correct
20 Correct 21 ms 47424 KB Output is correct
21 Correct 23 ms 47504 KB Output is correct
22 Correct 22 ms 47464 KB Output is correct
23 Correct 22 ms 47444 KB Output is correct
24 Correct 24 ms 47376 KB Output is correct
25 Correct 22 ms 47352 KB Output is correct
26 Correct 23 ms 47432 KB Output is correct
27 Correct 26 ms 47316 KB Output is correct
28 Correct 23 ms 47340 KB Output is correct
29 Correct 22 ms 47440 KB Output is correct
30 Correct 615 ms 163672 KB Output is correct
31 Correct 772 ms 176112 KB Output is correct
32 Correct 799 ms 246892 KB Output is correct
33 Correct 598 ms 227564 KB Output is correct
34 Correct 599 ms 227652 KB Output is correct
35 Correct 598 ms 225168 KB Output is correct
36 Correct 551 ms 201712 KB Output is correct
37 Correct 581 ms 189824 KB Output is correct
38 Correct 616 ms 188852 KB Output is correct
39 Correct 577 ms 188844 KB Output is correct
40 Correct 620 ms 190284 KB Output is correct
41 Correct 735 ms 186560 KB Output is correct
42 Correct 793 ms 198684 KB Output is correct
43 Correct 707 ms 230780 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47444 KB Output is correct
2 Correct 22 ms 47416 KB Output is correct
3 Correct 22 ms 47480 KB Output is correct
4 Correct 22 ms 47420 KB Output is correct
5 Correct 22 ms 47368 KB Output is correct
6 Correct 23 ms 47416 KB Output is correct
7 Correct 23 ms 47476 KB Output is correct
8 Incorrect 24 ms 47488 KB 3rd lines differ - on the 1st token, expected: '10478', found: '10490'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47228 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Correct 23 ms 47268 KB Output is correct
4 Correct 20 ms 47188 KB Output is correct
5 Correct 21 ms 47188 KB Output is correct
6 Correct 21 ms 47188 KB Output is correct
7 Correct 21 ms 47272 KB Output is correct
8 Correct 20 ms 47188 KB Output is correct
9 Correct 22 ms 47304 KB Output is correct
10 Correct 20 ms 47252 KB Output is correct
11 Correct 21 ms 47304 KB Output is correct
12 Correct 21 ms 47192 KB Output is correct
13 Correct 21 ms 47232 KB Output is correct
14 Correct 21 ms 47284 KB Output is correct
15 Correct 21 ms 47188 KB Output is correct
16 Correct 21 ms 47292 KB Output is correct
17 Correct 22 ms 47296 KB Output is correct
18 Correct 21 ms 47196 KB Output is correct
19 Correct 21 ms 47316 KB Output is correct
20 Correct 21 ms 47424 KB Output is correct
21 Correct 23 ms 47504 KB Output is correct
22 Correct 22 ms 47464 KB Output is correct
23 Correct 22 ms 47444 KB Output is correct
24 Correct 24 ms 47376 KB Output is correct
25 Correct 22 ms 47352 KB Output is correct
26 Correct 23 ms 47432 KB Output is correct
27 Correct 26 ms 47316 KB Output is correct
28 Correct 23 ms 47340 KB Output is correct
29 Correct 22 ms 47440 KB Output is correct
30 Correct 615 ms 163672 KB Output is correct
31 Correct 772 ms 176112 KB Output is correct
32 Correct 799 ms 246892 KB Output is correct
33 Correct 598 ms 227564 KB Output is correct
34 Correct 599 ms 227652 KB Output is correct
35 Correct 598 ms 225168 KB Output is correct
36 Correct 551 ms 201712 KB Output is correct
37 Correct 581 ms 189824 KB Output is correct
38 Correct 616 ms 188852 KB Output is correct
39 Correct 577 ms 188844 KB Output is correct
40 Correct 620 ms 190284 KB Output is correct
41 Correct 735 ms 186560 KB Output is correct
42 Correct 793 ms 198684 KB Output is correct
43 Correct 707 ms 230780 KB Output is correct
44 Correct 22 ms 47444 KB Output is correct
45 Correct 22 ms 47416 KB Output is correct
46 Correct 22 ms 47480 KB Output is correct
47 Correct 22 ms 47420 KB Output is correct
48 Correct 22 ms 47368 KB Output is correct
49 Correct 23 ms 47416 KB Output is correct
50 Correct 23 ms 47476 KB Output is correct
51 Incorrect 24 ms 47488 KB 3rd lines differ - on the 1st token, expected: '10478', found: '10490'
52 Halted 0 ms 0 KB -