Submission #835650

#	Time	Username	Problem	Language	Result	Execution time	Memory
835650		lollipop	Radio Towers (IOI22_towers)	C++17	100 / 100	1272 ms	27740 KiB

towers

#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 1000000000000000
#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 = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;

#include "towers.h"


// first type of segment tree 
struct stu{
	int mn , mx , val , val1 , pos ; 
};
stu node[ 4 * N ] , xx ;
int a[ N ] , n ; 

stu combine( stu a , stu b ){
	stu c ; c.mx = max( a.mx , b.mx ) ;
	c.mn = min( a.mn , b.mn ) ;
	c.val = max( { a.val , b.val , b.mx - a.mn } ) ;
	c.val1 = max( { a.val1 , b.val1 , a.mx - b.mn } ) ;
	if( a.mn < b.mn ) c.pos = a.pos ;
	else c.pos = b.pos ; 
	return c ; 
}
void build( int v , int vl , int vr ){
	if( vl == vr ){
		node[ v ] = { a[ vl ] , a[ vl ] , 0 , 0 , vl } ;
		return ;
	}
	int vm = ( vl + vr ) / 2 ;
	build( v + v , vl , vm ) ;
	build( v + v + 1 , vm + 1 , vr ) ;
	node[ v ] = combine( node[ v + v ] , node[ v + v + 1 ] ) ;
}
stu get_df( int v , int vl , int vr , int l , int r ){
	if( l > r ) return xx ;
	if( vl == l && vr == r ) return node[ v ] ;
	int vm = ( vl + vr ) / 2 ;
	stu a , b ;
	a = get_df( v + v , vl , vm , l , min( r , vm ) ) ;
	b = get_df( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
	return combine( a , b ) ;  
}
int get_clos( int v , int vl , int vr , int l , int r , int val , int nd ){
	if( l > r ) return -1 ;	
	if( node[ v ].mx < val ) return -1 ;
	if( vl == vr ) return vl ; 
	int vm = ( vl + vr ) / 2 ; 
	// nd == -1 --> marcxnidan
	// nd == 1 --> marjvnidan
	if( nd == -1 ){
		int x = -1 ;
		if( node[ v + v + 1 ].mx >= val ){
			x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ;
		}
		if( x == -1 ) 
		 x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ; 
		return x ; 
	}
	else{
		int x = -1 ;
		if( node[ v + v ].mx >= val ){
			x = get_clos( v + v , vl , vm , l , min( r , vm ) , val , nd ) ; 
		}
		if( x == -1 ) 
		 x = get_clos( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r , val , nd ) ; 
		return x ; 		
	}
}

// now you need a new persistent_seg_tree with decreasing Diff 
// anu ginda jami da yvelaze marcx_yvelaze_marjv

int clos_l[ N ] , clos_r[ N ] ; 
map < int , int > lst ; 

int cc = 2 ;
pair < int , int > sn[ 20 * N ] ;
int jm[ 20 * N ] ;

void build_ot( int v , int vl , int vr ){
	if( vl == vr ){
		jm[ v ] = 0 ; return ;
	}
	int vm = ( vl + vr ) / 2 ;
	sn[ v ].f = cc ; cc ++ ; 
	build_ot( sn[ v ].f , vl , vm ) ;
	sn[ v ].s = cc ; cc ++ ;
	build_ot( sn[ v ].s , vm + 1 , vr ) ;
	jm[ v ] = 0 ; 
	return ;
}
void update_ot( int v , int pp , int vl , int vr , int pos ){
	if( vl == vr ){
		jm[ v ] = 1 ; 
		return ;  
	}
	int vm = ( vl + vr ) / 2 ;
	if( vm >= pos ){
	   sn[ v ].f = cc ; cc ++ ; 
	   sn[ v ].s = sn[ pp ].s ;
	   update_ot( sn[ v ].f , sn[ pp ].f , vl , vm , pos ) ; 
	}
	else{
	   sn[ v ].s = cc ; cc ++ ; 
	   sn[ v ].f = sn[ pp ].f ;
	   update_ot( sn[ v ].s , sn[ pp ].s , vm + 1 , vr , pos ) ; 		
	}
	jm[ v ] = jm[ sn[ v ].f ] + jm[ sn[ v ].s ] ;
}

int sum( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ) return jm[ v ] ;
	int vm = ( vl + vr ) / 2 ;
	int a , b ;
	a = sum( sn[ v ].f , vl , vm , l , min( r , vm ) ) ;
	b = sum( sn[ v ].s , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return ( a + b ) ; 
}
int get_ert( int v , int vl , int vr , int l , int r , int tp ){
	if( l > r ) return -1 ; 
	if( jm[ v ] == 0 ) return -1 ;	
	if( vl == vr ) return vl ;
	int vm = ( vl + vr ) / 2 ;
	// -1 --> marcxena
	// 1 --> marjvena
	if( tp == -1 ){
		int x = -1 ;
		if( jm[ sn[ v ].f ] != 0 ){
			x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ; 
		}
		if( x == -1 ) x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
		return x ; 
	}
	else{
		int x = -1 ;
		if( jm[ sn[ v ].s ] != 0 ){
			x = get_ert( sn[ v ].s , vm + 1 , vr , max( l , vm + 1 ) , r , tp ) ;
		}
		if( x == -1 ) x = get_ert( sn[ v ].f , vl , vm , l , min( r , vm ) , tp ) ; 
		return x ; 		
	}
}
set < pair < int , int > > se ; 
stack < int > st ; set < int > sis ; 
void init(int N, std::vector<int> H){
    n = N ; FOR( i , N ) a[ i + 1 ] = H[ i ] ;
    // if this works make it into segment tree ?
    xx.mn = 1e9 + 1 ; xx.mx = -1e9 - 1 ; xx.val = 0 ; xx.val1 = 0 ; xx.pos = -1 ;
    build( 1 , 1 , n ) ;
    build_ot( 1 , 1 , n ) ;
	// left to right  
    for( int j = 1 ; j <= n ; j ++ ){
    	while( true ){
    		if( st.size() == 0 ) break ;
    		if( a[ st.top() ] > a[ j ] ){
    			st.pop() ; 
			} else break ; 
		}
		if( st.size() == 0 ){
			clos_l[ j ] = 0 ; 
		} else clos_l[ j ] = st.top() ; 
		st.push( j ) ; 
	}
    // right to left 
    while( st.size() > 0 ) st.pop() ;
    for( int j = n ; j >= 1 ; j -- ){
    	while( true ){
    		if( st.size() == 0 ) break ;
    		if( a[ st.top() ] > a[ j ] ){
    			st.pop() ; 
			} else break ; 
		}
		if( st.size() == 0 ){
			clos_r[ j ] = n + 1 ; 
		} else clos_r[ j ] = st.top() ; 
		st.push( j ) ; 
	}    
	vector < pair < int , int > > v ;
	for( int j = 1 ; j <= n ; j ++ ){
		if( clos_l[ j ] == j - 1 || clos_r[ j ] == j + 1 ) continue ;
		stu bb = get_df( 1 , 1 , n , clos_l[ j ] + 1 , j ) ;
		stu aa = get_df( 1 , 1 , n , j , clos_r[ j ] - 1 ) ;
		bb.mx = min( bb.mx , aa.mx ) ; 
		int af = bb.mx - a[ j ] ;
		v.pb( { af , j } ) ; 
		//cout << af << " " << j << endl ;
	}
	sort( v.begin() , v.end() ) ; 	
    // now slowly create persistent seg tree
    int bef = 1 ;
    for( int j = v.size() - 1 ; j >= 0 ; j -- ){
    	pair < int , int > p ; 
    	p = v[ j ] ; 
    	int cur = cc ; cc ++ ;
    	lst[ p.f ] = cur ; 
    	update_ot( cur , bef , 1 , n , p.s ) ;
    	bef = cur ; 
    	sis.insert( p.f ) ; 
	}
    for( auto x : sis ){
    	se.insert( { x , lst[ x ] } ) ; 
	}   
}

int check( int l , int r , int pos , int tp , int d ){
	// -1 --> marcxnidan
	// 1 --> marjvnidan
	if( tp == -1 ){
		int xix = get_clos( 1 , 1 , n , l , pos , a[ pos ] + 1 , -1 ) ;
		if( xix == -1 ) return 0 ;
		stu ch = get_df( 1 , 1 , n , l , xix ) ; 
		if( ch.val < d ) return 0 ;
		return 1 ; 
	}
	if( tp == 1 ){
		int xix = get_clos( 1 , 1 , n , pos , r , a[ pos ] + 1 , 1 ) ;
		if( xix == -1 ) return 0 ;
		stu ch = get_df( 1 , 1 , n , xix , r ) ; 
		if( ch.val1 < d ) return 0 ;
		return 1 ; 
	}	
}
int max_towers(int L, int R, int D){
   L ++ ; R ++ ;    
   pair < int , int > p ; p.s = 1 ;
   if( se.size() != 0 )
   if( (*(--se.end() )).f >= D ) 
   p = *(se.lower_bound( { D , 0 } ) ) ; 
   int root = p.s ; 
   // now calculate the answerr 
   int ans = sum( root , 1 , n , L , R ) ;
  // if( L == 1 && R == n ) return ans ;
   if( ans == 0 ){
   	 stu cur ; cur = get_df( 1 , 1 , n , L , R ) ;
   	 int pos = cur.pos ; 
   	 if( check( L , R , pos , -1 , D ) == 1 || check( L , R , pos , 1 , D ) == 1 ) return 2 ;
   	 return 1 ;
   }
   // else we have left_right
   int lf = get_ert( root , 1 , n , L , R , -1 ) ;
   int rg = get_ert( root , 1 , n , L , R , 1 ) ;
  // cout << lf << " " << rg << endl ;
   if( lf != -1 )
   ans = ans + check( L , R , lf , -1 , D ) ;
   if( rg != -1 )
   ans = ans + check( L , R , rg , 1 , D ) ;
   return ans ;
   
}


// int main() {
//   int N, Q;
//   assert(2 == scanf("%d %d", &N, &Q));
//   std::vector<int> H(N);
//   for (int i = 0; i < N; ++i) {
//     assert(1 == scanf("%d", &H[i]));
//   }
//   init(N, H);
//
//   for (int i = 0; i < Q; ++i) {
//     int L, R, D;
//     assert(3 == scanf("%d %d %d", &L, &R, &D));
//     printf("%d\n", max_towers(L, R, D));
//   }
//   return 0;
// }

Compilation message (stderr)

towers.cpp: In function 'int check(int, int, int, int, int)':
towers.cpp:252:1: warning: control reaches end of non-void function [-Wreturn-type]
  252 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23