| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996774 |
2024-06-11T07:48:09 Z |
lollipop |
Zoltan (COCI16_zoltan) |
C++17 |
|
303 ms |
26588 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 = 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
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 ;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5976 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5976 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
5980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
5980 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 11 |
Correct |
194 ms |
24308 KB |
Output is correct |
| 12 |
Correct |
162 ms |
23048 KB |
Output is correct |
| 13 |
Correct |
145 ms |
18516 KB |
Output is correct |
| 14 |
Correct |
201 ms |
23116 KB |
Output is correct |
| 15 |
Correct |
242 ms |
24956 KB |
Output is correct |
| 16 |
Correct |
303 ms |
26588 KB |
Output is correct |
| 17 |
Correct |
204 ms |
25680 KB |
Output is correct |
| 18 |
Correct |
212 ms |
25748 KB |
Output is correct |
| 19 |
Correct |
218 ms |
25680 KB |
Output is correct |
| 20 |
Correct |
215 ms |
25680 KB |
Output is correct |
