제출 #574422

#제출 시각아이디문제언어결과실행 시간메모리
574422chonkaMisspelling (JOI22_misspelling)C++17
100 / 100
1885 ms286684 KiB
#include<bits/stdc++.h> using namespace std ; typedef long long ll ; const int MAXN = 500007 ; const int MOD = 1000000007 ; const int SIGMA = 26 , LOG = 20 ; int n ; int small[ MAXN ] , large[ MAXN ] ; ll dp[ MAXN ][ SIGMA ] ; int rmq[ 2 ][ LOG ][ MAXN ] ; int mxpw[ MAXN ] ; void input ( ) { int m ; cin >> n >> m ; for ( int x , y , i = 1 ; i <= m ; ++ i ) { cin >> x >> y ; if ( x < y ) { large[ x ] = max ( large[ x ] , y ) ; } else if ( x > y ) { small[ y ] = max ( small[ y ] , x ) ; } } for ( int i = 1 ; i <= n ; ++ i ) { rmq[ 0 ][ 0 ][ i ] = large[ i ] ; rmq[ 1 ][ 0 ][ i ] = small[ i ] ; } for ( int id : { 0 , 1 } ) { for ( int lvl = 1 ; lvl < LOG ; ++ lvl ) { for ( int i = 1 ; i + ( 1 << lvl ) - 1 <= n ; ++ i ) { rmq[ id ][ lvl ][ i ] = max ( rmq[ id ][ lvl - 1 ][ i ] , rmq[ id ][ lvl - 1 ][ i + ( 1 << ( lvl - 1 ) ) ] ) ; } } } mxpw[ 1 ] = 0 ; for ( int i = 2 ; i <= n ; ++ i ) { mxpw[ i ] = mxpw[ i - 1 ] ; if ( ( 1 << ( mxpw[ i ] + 1 ) ) < i ) { ++ mxpw[ i ] ; } } } int get_mx ( int id , int l , int r ) { if ( l > r ) { return 0 ; } int len = ( 1 << mxpw[ r - l + 1 ] ) ; return max ( rmq[ id ][ mxpw[ r - l + 1 ] ][ l ] , rmq[ id ][ mxpw[ r - l + 1 ] ][ r - len + 1 ] ) ; } int f ( int id , int targ ) { int l , r , mid ; l = 0 , r = targ - 1 ; while ( r - l > 3 ) { mid = ( l + r ) / 2 ; if ( get_mx ( id , mid + 1 , targ - 1 ) < targ ) { r = mid ; } else { l = mid + 1 ; } } while ( get_mx ( id , l + 1 , targ - 1 ) >= targ ) { ++ l ; } return l ; } ll sm[ SIGMA ] ; ll add[ MAXN ][ SIGMA ] ; void solve ( ) { for ( int i = n ; i >= 1 ; -- i ) { int id_large = f ( 1 , i ) ; int id_small = f ( 0 , i ) ; for ( int j = 0 ; j < SIGMA ; ++ j ) { sm[ j ] = ( sm[ j ] + add[ i ][ j ] + MOD ) % MOD ; dp[ i ][ j ] = sm[ j ] ; if ( id_large < n && id_small < n ) { dp[ i ][ j ] = ( dp[ i ][ j ] + 1 ) % MOD ; } } for ( int j = 0 ; j < SIGMA ; ++ j ) { for ( int t = 0 ; t < SIGMA ; ++ t ) { if ( t == j ) { continue ; } sm[ t ] = ( sm[ t ] + dp[ i ][ j ] ) % MOD ; } for ( int t = j + 1 ; t < SIGMA ; ++ t ) { add[ id_large ][ t ] = ( add[ id_large ][ t ] - dp[ i ][ j ] + MOD ) % MOD ; } for ( int t = 0 ; t < j ; ++ t ) { add[ id_small ][ t ] = ( add[ id_small ][ t ] - dp[ i ][ j ] + MOD ) % MOD ; } } } ll ans = 0 ; for ( int i = 0 ; i < SIGMA ; ++ i ) { ans = ( ans + dp[ 1 ][ i ] ) % MOD ; } cout << ans << "\n" ; } int main ( ) { ios_base :: sync_with_stdio ( false ) ; cin.tie ( NULL ) ; int t ; /// cin >> t ; ///scanf ( "%d" , &t ) ; t = 1 ; while ( t -- ) { input ( ) ; solve ( ) ; } return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...