이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |