oj.uz

Submission #631478

# Submission time Handle Problem Language Result Execution time Memory
631478 2022-08-18T07:35:06 Z mdn2002 Misspelling (JOI22_misspelling) C++14
100 / 100
 2854 ms 378856 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1743 ms 372096 KB Output is correct
6 Correct 1727 ms 378748 KB Output is correct
7 Correct 1737 ms 378724 KB Output is correct
8 Correct 1747 ms 378680 KB Output is correct
9 Correct 1730 ms 378856 KB Output is correct
10 Correct 60 ms 15384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1760 ms 378820 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 64 ms 15116 KB Output is correct
27 Correct 78 ms 15008 KB Output is correct
28 Correct 84 ms 15032 KB Output is correct
29 Correct 64 ms 15152 KB Output is correct
30 Correct 65 ms 15176 KB Output is correct
31 Correct 267 ms 15140 KB Output is correct
32 Correct 61 ms 15152 KB Output is correct
33 Correct 60 ms 15164 KB Output is correct
34 Correct 69 ms 15168 KB Output is correct
35 Correct 269 ms 15124 KB Output is correct
36 Correct 92 ms 14820 KB Output is correct
37 Correct 76 ms 15120 KB Output is correct
38 Correct 77 ms 15184 KB Output is correct
39 Correct 86 ms 15200 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1743 ms 372096 KB Output is correct
31 Correct 1727 ms 378748 KB Output is correct
32 Correct 1737 ms 378724 KB Output is correct
33 Correct 1747 ms 378680 KB Output is correct
34 Correct 1730 ms 378856 KB Output is correct
35 Correct 60 ms 15384 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1760 ms 378820 KB Output is correct
39 Correct 64 ms 15116 KB Output is correct
40 Correct 78 ms 15008 KB Output is correct
41 Correct 84 ms 15032 KB Output is correct
42 Correct 64 ms 15152 KB Output is correct
43 Correct 65 ms 15176 KB Output is correct
44 Correct 267 ms 15140 KB Output is correct
45 Correct 61 ms 15152 KB Output is correct
46 Correct 60 ms 15164 KB Output is correct
47 Correct 69 ms 15168 KB Output is correct
48 Correct 269 ms 15124 KB Output is correct
49 Correct 92 ms 14820 KB Output is correct
50 Correct 76 ms 15120 KB Output is correct
51 Correct 77 ms 15184 KB Output is correct
52 Correct 86 ms 15200 KB Output is correct
53 Correct 2130 ms 372636 KB Output is correct
54 Correct 2482 ms 371468 KB Output is correct
55 Correct 2044 ms 378348 KB Output is correct
56 Correct 2143 ms 378332 KB Output is correct
57 Correct 2076 ms 378632 KB Output is correct
58 Correct 2045 ms 378628 KB Output is correct
59 Correct 2088 ms 378636 KB Output is correct
60 Correct 2323 ms 378664 KB Output is correct
61 Correct 2854 ms 364204 KB Output is correct
62 Correct 2484 ms 376952 KB Output is correct
63 Correct 2493 ms 375356 KB Output is correct
64 Correct 2718 ms 373708 KB Output is correct