Submission #996772

#	Time	Username	Problem	Language	Result	Execution time	Memory
996772		lollipop	Zoltan (COCI16_zoltan)	C++17	21 / 140	272 ms	26640 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 ) ; 
	long long bb = 0 ; 
	if( a.num == c.num ) bb += a.cnt ;
	if( b.num == c.num ) bb += b.cnt ;
	bb %= mod ;  
	c.cnt %= bb ; 
	return c ; 
}
 
void update( int v , int vl , int vr , int pos , int numb , int cc ){
	 if( vl == vr ){
	 	arr[ pos ] = numb ;
	 	long long nw = node[ v ].cnt ; 
	 	if( node[ v ].num == numb ) nw += cc ;
	 	else 
		 nw = cc ; 
		 nw %= mod ; 
		 node[ v ].cnt = nw ;
	 	node[ v ].num = numb ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm < pos ) update( v + v + 1 , vm + 1 , vr , pos , numb , cc ) ;
	 else update( v + v , vl , vm , pos , numb , cc ) ;
	 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 , int cc ){
	 if( vl == vr ){
	 	arr1[ pos ] = numb ;
	 	long long nw = node1[ v ].cnt ; 
	 	if( node1[ v ].num == numb ) nw += cc ;
	 	else 
		 nw = cc ; 
		 nw %= mod ; 
		 node1[ v ].cnt = nw ; 
	 	node1[ v ].num = numb ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm < pos ) update1( v + v + 1 , vm + 1 , vr , pos , numb , cc) ;
	 else update1( v + v , vl , vm , pos , numb , cc ) ;
	 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 ] ;	
set < int > s ;
vector < int > v( N ); 
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); 
    int n ; 
    cin >> 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 ) ; 
		 if( M.cnt == 0 ) M.cnt = 1 ;
		 if( L.cnt == 0 ) L.cnt = 1 ;
		 update( 1 , 1 , st , x , M.num + 1 , M.cnt ) ; 
		 update1( 1 , 1 , st , x , L.num + 1 , L.cnt ) ; 
		 		 
		 
		 long long aaa = M.cnt ;
		 long long xx = L.cnt ; 
		 aaa = aaa * xx ; aaa %= mod ;
		 long long kk = xar[ n - mx ] ; 
		 aaa = aaa * kk ; aaa %= mod ;
		 aaa = aaa + ans[ mxx ] ; 
		 aaa %= mod ; 
		 ans[ mxx ] = aaa ; 
 
	}
	long long int aaa = ans[ mx ] ;
	
	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 ++ )
      | 
zoltan.cpp: In function 'void update(int, int, int, int, int, int)':
zoltan.cpp:43:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   43 |    else
      |    ^~~~
zoltan.cpp:45:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   45 |    nw %= mod ;
      |    ^~
zoltan.cpp: In function 'void update1(int, int, int, int, int, int)':
zoltan.cpp:73:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   73 |    else
      |    ^~~~
zoltan.cpp:75:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   75 |    nw %= mod ;
      |    ^~

• Subtask 1: 21 / 140