| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 996771 | 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 = 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 ;
}