Submission #996762

#TimeUsernameProblemLanguageResultExecution timeMemory
996762lollipopZoltan (COCI16_zoltan)C++17
21 / 140
248 ms25860 KiB
#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 ) ; update( 1 , 1 , st , x , M.num + 1 , M.cnt ) ; update1( 1 , 1 , st , x , L.num + 1 , L.cnt ) ; // M = get( 1 , 1 , st , x , x ) ; // L = get1( 1 , 1 , st , x , x ) ; 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 (stderr)

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 timeMemoryGrader output
Fetching results...