Submission #577280

#	Time	Username	Problem	Language	Result	Execution time	Memory
577280		lollipop	Zoltan (COCI16_zoltan)	C++17	7 / 140	428 ms	35928 KiB

zoltan

#include<bits/stdc++.h>
#define int 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 FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
#define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
using namespace std ;
const int mod =  1000000007 ;
const int mod1 = 998244353 ; 
const int N = 2e5 + 10 ; 
map < int , int > ma , ma1 ; 
struct stu{
	int num ;
	int cnt ; 
};
int arr[ 200005 ] ;
stu node[ 4 * N ] ;
stu merge( stu a , stu b ){
	stu c ; 
	c.num = max( a.num , b.num ) ; 
	if( a.cnt == c.cnt ) c.cnt += a.cnt ;
	if( b.cnt == c.cnt ) c.cnt += b.cnt ; 
	return c ; 
}
void build( int v , int vl , int vr ){
	 if( vl == vr ){
	 	node[ v ].num = arr[ vl ] ;
	 	node[ v ].cnt = 1 ;
	 	return ;
	 }
	 int vm = ( vl + vr ) / 2 ;
	 build( v + v , vl , vm ) ;
	 build( v + v + 1 , vm + 1 , vr ) ; 
	 node[ v ] = merge( node[ v + v ] , node[ v + v + 1 ] ) ; 
}
void update( int v , int vl , int vr , int pos , int numb ){
	 if( vl == vr ){
	 	arr[ pos ] = numb ;
	 	node[ v ].num = numb ;
	 	node[ v ].cnt = 1 ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm < pos ) update( v + v + 1 , vm + 1 , vr , pos , numb ) ;
	 else update( v + v , vl , vm , pos , numb ) ;
	 node[ v ] = merge( node[ v + v ] , node[ v + v + 1 ] ) ;
}
stu get( int v , int vl , int vr , int l , int r ){
	if( l > r ) return { 0 , 0 } ; 
	if( vl == l && vr == r  ){
		return node[ v ] ;
	}
	int vm = ( vl + vr ) / 2 ; 
	return merge( get( v + v , vl , vm , l , min( r , vm ) ) 
    , get( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ) ; 
}
stu node1[ 4 * N ] ; 
// second seg tree 
int arr1[ 200005 ] ;
void build1( int v , int vl , int vr ){
	 if( vl == vr ){
	 	node1[ v ].num = arr1[ vl ] ;
	 	node1[ v ].cnt = 1 ;
	 	return ;
	 }
	 int vm = ( vl + vr ) / 2 ;
	 build1( v + v , vl , vm ) ;
	 build1( v + v + 1 , vm + 1 , vr ) ; 
	 node1[ v ] = merge( node1[ v + v ] , node1[ v + v + 1 ] ) ; 
}
void update1( int v , int vl , int vr , int pos , int numb ){
	 if( vl == vr ){
	 	arr1[ pos ] = numb ;
	 	node1[ v ].num = numb ;
	 	node1[ v ].cnt = 1 ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm < pos ) update1( v + v + 1 , vm + 1 , vr , pos , numb ) ;
	 else update1( v + v , vl , vm , pos , numb ) ;
	 node1[ v ] = merge( node1[ v + v ] , node1[ v + v + 1 ] ) ;
}
stu get1( int v , int vl , int vr , int l , int r ){
	if( l > r ) return { 0 , 0 } ; 
	if( vl == l && vr == r  ){
		return node1[ v ] ;
	}
	int vm = ( vl + vr ) / 2 ; 
	return merge( get1( v + v , vl , vm , l , min( r , vm ) ) 
    , get1( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ) ; 
}
int ans[ 200005 ] ; 
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); 
    int n ; 
    cin >> n ; 
	set < int > s ;
	vector < int > v( n ); 
	int st = 1 ;
	FOR( i , n ){
		cin >> v[ i ] ;
		s.insert( v[ i ] ) ; 
	}
	while( s.size() > 0 ){
		int x = *s.begin() ; 
		ma[ x ] = st ; 
		st ++ ; 
		s.erase( s.begin() ) ; 
	}
	st -- ; 
	int mx = 0 ; 
	FOR( i , n ) v[ i ] = ma[ v[ i ] ] ; 
	build1( 1 , 1 , st ) ;
	build( 1 , 1 , st ) ;
	for( int j = n - 1 ; j >= 0 ; j -- ){
		 int x = v[ j ] ; 
		 stu M , L ; 
		 M = get( 1 , 1 , st , x + 1 , st ) ; 
		 L = get1( 1 , 1 , st , 1 , x - 1 ) ;
		 int mxx = M.num + L.num + 1 ; 
		 mx = max( mx , mxx ) ; 
		 if( M.num == 0 && L.num == 0 ) ans[ mxx ] += 2 ;
		 else
		 ans[ mxx ] = ans[ mxx ] + M.cnt * L.cnt % mod ; 
		 ans[ mxx ] %= mod ; 
		 update( 1 , 1 , st , x , M.num + 1 ) ; 
		 update1( 1 , 1 , st , x , L.num + 1 ) ;  
	}
	cout << mx << " " << max(  1LL , ans[ mx ] ) ;
}

Compilation message (stderr)

zoltan.cpp:10: warning: "FOR" redefined
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
zoltan.cpp:9: note: this is the location of the previous definition
    9 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
      | 
zoltan.cpp:11: warning: "FOR" redefined
   11 | #define FOR( k , n ) for( int k = 0 ; k < n ; k ++ )
      | 
zoltan.cpp:10: note: this is the location of the previous definition
   10 | #define FOR( j , n ) for( int j = 0 ; j < n ; j ++ )
      | 
zoltan.cpp: In function 'stu merge(stu, stu)':
zoltan.cpp:26:17: warning: 'c.stu::cnt' is used uninitialized in this function [-Wuninitialized]
   26 |  if( a.cnt == c.cnt ) c.cnt += a.cnt ;
      |               ~~^~~

• Subtask 1: 7 / 140