Submission #631454

#	Time	Username	Problem	Language	Result	Execution time	Memory
631454		mdn2002	Misspelling (JOI22_misspelling)	C++14	60 / 100	4037 ms	51192 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 tree [2000006][28];
void up ( int nod , int l , int r , int x , int val , int car )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        tree [nod][car] = ( tree [nod][car] + val ) % mod;
        return;
    }
    int mid = ( l + r ) / 2;
    up ( nod * 2 , l , mid , x , val , car );
    up ( nod * 2 + 1 , mid + 1 , r , x , val , car );
    tree [nod][car] = ( tree [ nod * 2 ][car] + tree [ nod * 2 + 1 ][car] ) % mod;
}
long long qr ( int nod , int l , int r , int x , int y , int car )
{
    if ( y < l || r < x ) return 0;
    if ( x <= l && r <= y ) return tree [nod][car];
    int mid = ( l + r ) / 2;
    return ( qr ( nod * 2 , l , mid , x , y , car ) + qr ( nod * 2 + 1 , mid + 1 , r , x , y , car ) ) % mod;
}
int main()
{
    cin >> n >> m;
    for ( int i = 1 ; 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 );
        }
        if ( x > y )
        {
            in [y] = min ( in [y] , x );
            inmx [y] = max ( inmx [y] , x );
        }
    }
    for ( int i = 0 ; i < 26 ; i ++ ) up ( 1 , 0 , n , 1 , 1 , i );
    for ( int i = 2 ; i <= n ; i ++ )
    {
        int lde = i , lin = i;
        for ( int j = i - 1 ; j >= 1 ; j -- )
        {
            if ( demx [j] >= i ) break;
            lin = j;
        }
        if ( lin != i )
        {
            for ( int j = 0 ; j < 26 ; j ++ )
            {
                long long sum = 0;
                for ( int z = j + 1 ; z < 26 ; z ++ ) sum = ( sum + qr ( 1 , 0 , n , lin , i - 1 , z ) ) % mod;
                up ( 1 , 0 , n , i , sum , j );
            }
        }

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

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