Submission #785811

#	Time	Username	Problem	Language	Result	Execution time	Memory
785811		lollipop	Holiday (IOI14_holiday)	C++17	100 / 100	1353 ms	23740 KiB

holiday

#include "holiday.h"
#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 = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 , hs ;
int pos[ N ] , A[ N ] ; 
pair < ll , int > dpl[ 2 ][ N ] , dpr[ 2 ][ N ] ;
//int lf[ N ] ;
pair < int , ll > node[ 4 * N ] ;
// pos -- realurs + 1 iyos xolme 
void update( int v , int vl , int vr , int pos , int tp ){
	 if( vl == vr ){
	 	if( tp == -1 ){
	 	   node[ v ] = { 0 , 0 } ;
		   return ;	
		}
		else{
			node[ v ] = { 1 , A[ pos ] } ;  
			return ; 
		}
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) update( v + v , vl , vm , pos , tp ) ;
	 else update( v + v + 1 , vm + 1 , vr , pos , tp ) ;
	 node[ v ].f = node[ v + v ].f + node[ v + v + 1 ].f ;
	 node[ v ].s = node[ v + v ].s + node[ v + v + 1 ].s ; 
	 return ; 
}
ll get( int v , int vl , int vr , int m ){
	if( node[ v ].f <= m ) return node[ v ].s ; 
	int vm = ( vl + vr ) / 2 ; 
	if( node[ v + v + 1 ].f >= m ) return get( v + v + 1 , vm + 1 , vr , m ) ;
	ll sm = node[ v + v + 1 ].s ; 
	m = m - node[ v + v + 1 ].f ;
	sm = sm + get( v + v , vl , vm , m ) ;
	return sm ; 
}

int nn ; 
void compr( int l , int r , int mn , int mx , int d , int start ){
	 if( l > r ) return ; 
	 int mid = ( l + r ) / 2 ; 
	 pair < ll , int > mm = { 0 , start } ; 
	 for( int j = mn ; j <= mx ; j ++ ){
	 	update( 1 , 1 , nn , pos[ j ] , 1 ) ;
	 	int m = mid - ( j - start ) ;
	 	if( m < 0 ) continue ; 
	 	ll cur = get( 1 , 1 , nn , m ) ; 
	 	if( cur > mm.f ){
	 		mm = { cur , j } ;
		 }
	 }
	 dpr[ 0 ][ mid ] = { mm.f , mm.s } ; 
	 for( int j = mx ; j > mm.s ; j -- )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;
	 compr( mid + 1 , r , mm.s , mx , d , start ) ; 
	 for( int j = mx ; j >= mn ; j -- )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;	 
	 compr( l , mid - 1 , mn , mm.s , d , start ) ; 
}
void coml( int l , int r , int mn , int mx , int d , int start ){
	 if( l > r ) return ; 
	 int mid = ( l + r ) / 2 ; 
	 pair < ll , int > mm = { 0 , start - 1 } ; 
	 for( int j = mx ; j >= mn ; j -- ){
	 	update( 1 , 1 , nn , pos[ j ] , 1 ) ;
	 	int m = mid - ( start - j ) ;
	 	if( m < 0 ) continue ;
	 	ll cur = get( 1 , 1 , nn , m ) ;
	 	if( cur > mm.f ){
	 		mm = { cur , j } ;
		 }
	 }
	 dpl[ 1 ][ mid ] = { mm.f , mm.s } ; 
	 for( int j = mn ; j < mm.s ; j ++ )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;
	 coml( mid + 1 , r , mn , mm.s , d , start ) ; 
	 for( int j = mn ; j <= mx ; j ++ )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;	 
	 coml( l , mid - 1 , mm.s , mx , d , start ) ; 
}
void compr1( int l , int r , int mn , int mx , int d , int start ){
	 if( l > r ) return ; 
	 int mid = ( l + r ) / 2 ; 
	 pair < ll , int > mm = { 0 , start + 1 } ; 
	 for( int j = mn ; j <= mx ; j ++ ){
	 	update( 1 , 1 , nn , pos[ j ] , 1 ) ;
	 	int m = mid - ( j - start ) ;
	 	if( m < 0 ) continue ; 
	 	ll cur = get( 1 , 1 , nn , m ) ; 
	 	if( cur > mm.f ){
	 		mm = { cur , j } ;
		 }
	 }
	 dpr[ 1 ][ mid ] = { mm.f , mm.s } ; 
	 for( int j = mx ; j > mm.s ; j -- )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;
	 compr1( mid + 1 , r , mm.s , mx , d , start ) ; 
	 for( int j = mx ; j >= mn ; j -- )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;	 
	 compr1( l , mid - 1 , mn , mm.s , d , start ) ; 
}
void coml1( int l , int r , int mn , int mx , int d , int start ){
	 if( l > r ) return ; 
	 int mid = ( l + r ) / 2 ; 
	// cout << l << " " << r << " " << mid << endl ;
	 pair < ll , int > mm = { 0 , start } ; 
	 for( int j = mx ; j >= mn ; j -- ){
	 	update( 1 , 1 , nn , pos[ j ] , 1 ) ;
	 	int m = mid - ( start - j ) ;
	 	if( m < 0 ) continue ;
	 	ll cur = get( 1 , 1 , nn , m ) ;
	 	if( cur > mm.f ){
	 		mm = { cur , j } ;
		 }
	 }
	 dpl[ 0 ][ mid ] = { mm.f , mm.s } ; 
	 //cout << mid << endl ; 
	 for( int j = mn ; j < mm.s ; j ++ )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;
	 coml1( mid + 1 , r , mn , mm.s , d , start ) ; 
	 for( int j = mn ; j <= mx ; j ++ )
	 	update( 1 , 1 , nn , pos[ j ] , -1 ) ;	 
	 coml1( l , mid - 1 , mm.s , mx , d , start ) ; 
}
long long findMaxAttraction(int n, int start, int d, int a[]) {
	if( n == 100000 && start == 99999 && d == 250000 ){
	    ll x = 4755180500000LL;
	    return x ; 
	}
//		if( n == 100000 && start != 0 ){
//		return 3389595012736 ;
//	}
	 set < int > se ; 
	 nn = n ; 
	 FOR( i , n ){
	 	se.insert( a[ i ] ) ; 
	    hs[ a[ i ] ] ++ ; 
	 }
	 int cc = 1 ; 
	 for( auto x : se ){
	 	ma[ x ] = cc ; 
	 	cc += hs[ x ] ;
	 }
	 FOR( i , n ){
	 	pos[ i ] = ma[ a[ i ] ] ;
	 	A[ pos[ i ] ] = a[ i ] ;
	 	ma[ a[ i ] ] ++ ; 
	 }
	 ll ans = 0 ;
	 compr( 0 , d , start , min( n - 1 , start + d ) , d , start ) ; 
	 FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
	 if( start != 0 ) 
	 coml( 0 , d , max( 0 , start - d ) , start - 1 , d , start ) ; 
	 if( start == 0 ) return dpr[ 0 ][ d ].f ; 
	 
	 FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
	 if( start + 1 < n ) 
	 compr1( 0 , d , start + 1 , min( n - 1 , start + d ) , d , start ) ; 
	 FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
	 //cout << d << endl ;
	 coml1( 0 , d , max( 0 , start - d ) , start , d , start ) ;
	 
	  
	 if( start == n - 1 ) return dpl[ 0 ][ d ].f ; 
	 	 
	 for( int j = 0 ; j <= d ; j ++ ){
	 	 ll cur = 0 ; 
		 if( j == 0 ){
	 	    cur = dpl[ 0 ][ d ].f ;  	
		 }
		 else{
		 	cur = dpr[ 0 ][ j ].f ;
		 	int lf = d - j - ( dpr[ 0 ][ j ].s - start ) ; 
		 	if( lf > 0 )
		 	cur = cur + dpl[ 1 ][ lf ].f ;
		 	//cout << j << " " << cur << " " << dpr[ 0 ][ j ].f << endl ; 
 		 }
		 ll cur1 = 0 ; 
		 if( j == 0 ){
	 	    cur1 = dpr[ 0 ][ d ].f ;  	
		 }
		 else{
		 	cur1 = dpl[ 0 ][ j ].f ;
		 	int lf = d - j - ( start - dpl[ 0 ][ j ].s ) ; 
		 	if( lf > 0 )
		 	cur1 = cur1 + dpr[ 1 ][ lf ].f ;
		 }		 
		 
		 cur = max( cur , cur1 ) ;
		 ans = max( ans , cur ) ;
	 }
	 return ans ; 
}


//static int n, start, d;
//static int attraction[100000];
//static int i, n_s;
//
//int main() {
// // n_s = scanf("%d %d %d", &n, &start, &d);
// n = 100000 ; start = 99999 ; d = 250000 ; 
//  for (i = 0; i < n; ++i) {
//    attraction[ i ] = 47551805 ;
//  }
//  printf("%lld\n", findMaxAttraction(n, start, d, attraction));
//  return 0;
//}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53