| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 577291 | lollipop | Zoltan (COCI16_zoltan) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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.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 ;
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 ;
int xar[ 200005 ] ;
xar[ 0 ] = 1 ;
for( int j = 1 ; j <= n ; j ++ ) xar[ j ] = xar[ j - 1 ] * 2 % 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 ) ;
ans[ mxx ] = ans[ mxx ] +max( 1LL , M.cnt ) * max( 1LL , L.cnt ) * xar[ n - j - mxx ]% mod ;
ans[ mxx ] %= mod ;
update( 1 , 1 , st , x , M.num + 1 ) ;
update1( 1 , 1 , st , x , L.num + 1 ) ;
}
if( mx == 1 ){
int ans = 1 ;
FOR( i , n ) ans = ( ans * 2 ) % mod ;
cout << mx << " " << ans ;
}
else
cout << mx << " " << ans[ mx ] ;
}