제출 #631478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631478		mdn2002	Misspelling (JOI22_misspelling)	C++14	100 / 100	2854 ms	378856 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
long long n , m , in [500005] , de [500005] , inmx [500005] , demx [500005] , mod = 1e9 + 7;
long long dp [500005][28] , st [500005][21][3] ;

int main()
{
    cin >> n >> m;
    for ( int i = 0 ; i <= n ; i ++ )
    {
        in [i] = 1e9;
        de [i] = 1e9;
    }
    for ( int i = 0 ; i < m ; i ++ )
    {
        long long x , y;
        cin >> x >> y;
        if ( x < y )
        {
            de [x] = min ( de [x] , y );
            demx [x] = max ( demx [x] , y );
            st [x][0][0] = max ( st [x][0][0] , y );
        }
        if ( x > y )
        {
            in [y] = min ( in [y] , x );
            inmx [y] = max ( inmx [y] , x );
            st [y][0][1] = max ( st [y][0][1] , x );
        }
    }
    for ( int i = 0 ; i < 2 ; i ++ )
    {
        for ( int j = 1 ; j <= 20 ; j ++ )
        {
            for ( int z = 1 ; z <= n ; z ++ )
            {
                st [z][j][i] = st [z][ j - 1 ][i];
                if ( z >= ( 1 << ( j - 1 ) ) ) st [z][j][i] = max ( st [z][j][i] , st [ z - ( 1 << ( j - 1 ) ) ][ j - 1 ][i] );
            }
        }
    }
    for ( int i = 0 ; i < 26 ; i ++ ) dp [1][i] = 1;
    for ( int i = 2 ; i <= n ; i ++ )
    {
        int lde = i , lin = i , x = i - 1;
        for ( int j = 20 ; j >= 0 ; j -- )
        {
            if ( x < ( 1 << j ) ) continue;
            if ( st [x][j][0] < i ) x -= ( 1 << j );
        }
        lin = x + 1;
        if ( lin != i )
        {
            for ( int j = 0 ; j < 26 ; j ++ )
            {
                long long sum = 0;
                for ( int z = j + 1 ; z < 26 ; z ++ ) sum = ( sum + dp [ i - 1 ][z] - dp [ lin - 1 ][z] + mod ) % mod;
                dp [i][j] = ( dp [i][j] + sum ) % mod;
            }
        }
        x = i - 1;
        for ( int j = 20 ; j >= 0 ; j -- )
        {
            if ( x < ( 1 << j ) ) continue;
            if ( st [x][j][1] < i ) x -= ( 1 << j );
        }
        lde = x + 1;


        if ( lde != i )
        {
            for ( int j = 0 ; j < 26 ; j ++ )
            {
                long long sum = 0;
                for ( int z = j - 1 ; z >= 0 ; z -- ) sum = ( sum + dp [ i - 1 ][z] - dp [ lde - 1 ][z] + mod ) % mod;
                dp [i][j] = ( dp [i][j] + sum ) % mod;
            }
        }
        for ( int j = 0 ; j < 26 ; j ++ ) dp [i][j] = ( dp [i][j] + dp [ i - 1 ][j] ) % mod;
    }
    long long sum = 0;
    for ( int i = 0 ; i < 26 ; i ++ ) sum = ( sum + dp [n][i] ) % mod;
    cout << sum;
}


/*
 2 2 1
 3 2 3
 4 4 3
 5 5 3
 6 6 6
 7 6 3
 */

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