Submission #996754

#	Time	Username	Problem	Language	Result	Execution time	Memory
996754		lollipop	Zoltan (COCI16_zoltan)	C++17	21 / 140	329 ms	27216 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 = 4e5 + 10 ; 
map < int , int > ma , ma1 ; 
//struct stu{
//	int num ;
//	int cnt ; 
//};
#define stu pair < int , int > 
#define num first
#define cnt second
int arr[ 400005 ] ;
stu node[ 4 * N ] ;
stu merge( stu a , stu b ){
	stu c ; 
	c.cnt = 0 ;
	c.num = max( a.num , b.num ) ; 
	if( a.num == c.num ) c.cnt += a.cnt ;
	if( b.num == c.num ) c.cnt += b.cnt ; 
	c.cnt %= mod ; 
	return c ; 
}

void update( int v , int vl , int vr , int pos , int numb ){
	 if( vl == vr ){
	 	arr[ pos ] = numb ;
//	 	if( node[ v ].num == numb ) node[ v ].cnt ++ ;
//	 	else 
		 node[ v ].cnt = 1 ; 
	 	node[ v ].num = numb ;
	 	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[ 400005 ] ;

void update1( int v , int vl , int vr , int pos , int numb ){
	 if( vl == vr ){
	 	arr1[ pos ] = numb ;
//	 	if( node1[ v ].num == numb ) node1[ v ].cnt ++ ;
//	 	else 
		 node1[ v ].cnt = 1 ; 
	 	node1[ v ].num = numb ;
	 	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[ 500005 ] ; 
int xar[ 500005 ] ;
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 ; 
	xar[ 0 ] = 1 ;
	for( int j = 1 ; j <= n ; j ++ ) xar[ j ] = xar[ j - 1 ] * 2LL % mod ; 
	FOR( i , n ) v[ i ] = ma[ v[ i ] ] ;
	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 ) ; 
		 long long aaa = ( max( 1 , M.cnt ) ) ;
		 aaa = aaa * max( 1 , L.cnt ) ;
		 aaa %= mod ; 
		 ans[ mxx ] = ans[ mxx ] + aaa ; 
		 ans[ mxx ] %= mod ; 
		 update( 1 , 1 , st , x , M.num + 1 ) ; 
		 update1( 1 , 1 , st , x , L.num + 1 ) ;  
	}
	long long int aaa = ans[ mx ] ;
	aaa = aaa * xar[ n - mx ] ;
	aaa %= mod ;
	
	cout << mx << " " << aaa;
}

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 ++ )
      |

• Subtask 1: 21 / 140