| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996766 |
2024-06-11T07:36:04 Z |
lollipop |
Zoltan (COCI16_zoltan) |
C++17 |
|
286 ms |
25680 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 = 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 ;
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 ;
if( node[ v ].num == numb ) node[ v ].cnt += cc ;
else
node[ v ].cnt = cc ;
node[ v ].cnt %= mod ;
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 ;
if( node1[ v ].num == numb ) node1[ v ].cnt += cc ;
else
node1[ v ].cnt = cc ;
node1[ v ].cnt %= mod ;
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 ] ;
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 ) ;
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 = ( max( 1 , M.cnt ) ) ;
aaa = aaa * max( 1 , L.cnt ) ;
aaa %= mod ; aaa = aaa * xar[ max( 0 , n - ( mx ) ) ] ;
aaa = aaa + ans[ mxx ] ;
aaa %= mod ;
ans[ mxx ] = aaa ;
}
long long int aaa = ans[ mx ] ;
aaa = aaa * xar[ n - mx ] ;
aaa %= mod ;
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 ++ )
|
zoltan.cpp: In function 'void update(int, int, int, int, int, int)':
zoltan.cpp:42:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
42 | else
| ^~~~
zoltan.cpp:44:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
44 | node[ v ].cnt %= mod ;
| ^~~~
zoltan.cpp: In function 'void update1(int, int, int, int, int, int)':
zoltan.cpp:70:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
70 | else
| ^~~~
zoltan.cpp:72:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
72 | node1[ v ].cnt %= mod ;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
4644 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 11 |
Incorrect |
173 ms |
23252 KB |
Output isn't correct |
| 12 |
Incorrect |
147 ms |
22060 KB |
Output isn't correct |
| 13 |
Incorrect |
138 ms |
17444 KB |
Output isn't correct |
| 14 |
Incorrect |
180 ms |
22096 KB |
Output isn't correct |
| 15 |
Incorrect |
219 ms |
24096 KB |
Output isn't correct |
| 16 |
Incorrect |
286 ms |
25680 KB |
Output isn't correct |
| 17 |
Incorrect |
171 ms |
25012 KB |
Output isn't correct |
| 18 |
Incorrect |
209 ms |
24912 KB |
Output isn't correct |
| 19 |
Incorrect |
190 ms |
24972 KB |
Output isn't correct |
| 20 |
Incorrect |
174 ms |
24916 KB |
Output isn't correct |
