Submission #631466

#	Time	Username	Problem	Language	Result	Execution time	Memory
631466		mdn2002	Misspelling (JOI22_misspelling)	C++14	60 / 100	4075 ms	137980 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
long long n , m , in [500005] , de [500005] , inmx [500005] , demx [500005] , inmxmx [500005] , demxmx [500005] , mod = 1e9 + 7;
long long tree [2000006][28] , tre [2000006][3];
long long dp [500005][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;
}

void upp ( int nod , int l , int r , int x , long long val , int wt )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        tre [nod][wt] = max ( tre [nod][wt] , val );
        return;
    }
    int mid = ( l + r ) / 2;
    upp ( nod * 2 , l , mid , x , val , wt );
    upp ( nod * 2 + 1 , mid + 1 , r , x , val , wt );
    tre [nod][wt] = max ( tre [ nod * 2 ][wt] , tre [ nod * 2 + 1 ][wt] );
}
long long qrr ( int nod , int l , int r , int x , int y , int wt )
{
    if ( y < l || r < x ) return 0;
    if ( x <= l && r <= y ) return tre [nod][wt];
    int mid = ( l + r ) / 2;
    return max ( qrr ( nod * 2 , l , mid , x , y , wt ) , qrr ( nod * 2 + 1 , mid + 1 , r , x , y , wt ) );
}
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 );
            upp ( 1 , 0 , n , x , y , 0 );
        }
        if ( x > y )
        {
            in [y] = min ( in [y] , x );
            inmx [y] = max ( inmx [y] , x );
            upp ( 1 , 0 , n , y , x , 1 );
        }
    }
    for ( int i = 0 ; i < 26 ; i ++ ) dp [1][i] = 1;
    for ( int i = 2 ; i <= n ; i ++ )
    {
        int lde = i , lin = i;
        int l = 1 , r = i , mid;
        while ( l < r )
        {
            //demxmx
            mid = ( l + r ) / 2;
            if ( qrr ( 1 , 0 , n , mid , i - 1 , 0 ) >= i ) l = mid + 1;
            else r = mid;
        }
        lin = l;
        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;
            }
        }

        l = 1 , r = i , mid;
        while ( l < r )
        {
            //inmxmx
            mid = ( l + r ) / 2;
            if ( qrr ( 1 , 0 , n , mid , i - 1 , 1 ) >= i ) l = mid + 1;
            else r = mid;
        }
        lde = l;
        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
 */

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:95:28: warning: right operand of comma operator has no effect [-Wunused-value]
   95 |         l = 1 , r = i , mid;
      |                            ^

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