Submission #574422

#	Time	Username	Problem	Language	Result	Execution time	Memory
574422		chonka	Misspelling (JOI22_misspelling)	C++17	100 / 100	1885 ms	286684 KiB

misspelling

#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 ;
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11