| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577292 |
2022-06-14T12:37:12 Z |
lollipop |
Zoltan (COCI16_zoltan) |
C++17 |
|
448 ms |
38900 KB |
#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 ] ;
}
Compilation message
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 ++ )
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1892 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
1888 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
1876 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
2024 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
2004 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
2004 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
2004 KB |
Output isn't correct |
| 11 |
Runtime error |
244 ms |
34372 KB |
Memory limit exceeded |
| 12 |
Incorrect |
193 ms |
32248 KB |
Output isn't correct |
| 13 |
Incorrect |
187 ms |
23248 KB |
Output isn't correct |
| 14 |
Runtime error |
266 ms |
32784 KB |
Memory limit exceeded |
| 15 |
Runtime error |
372 ms |
36264 KB |
Memory limit exceeded |
| 16 |
Runtime error |
448 ms |
38900 KB |
Memory limit exceeded |
| 17 |
Runtime error |
313 ms |
36244 KB |
Memory limit exceeded |
| 18 |
Runtime error |
281 ms |
36180 KB |
Memory limit exceeded |
| 19 |
Runtime error |
314 ms |
36128 KB |
Memory limit exceeded |
| 20 |
Runtime error |
310 ms |
36200 KB |
Memory limit exceeded |
