oj.uz

Submission #862510

# Submission time Handle Problem Language Result Execution time Memory
862510 2023-10-18T12:18:23 Z boris_mihov Misspelling (JOI22_misspelling) C++17
28 / 100
 4000 ms 80336 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 500000 + 10;
const int ALPHABET = 26;
const int MOD = 1e9 + 7;

int n, m;
int l[MAXN];
int r[MAXN];
int type[MAXN];
int dp[MAXN][ALPHABET];
bool bl[MAXN][ALPHABET];
std::vector <int> begin[MAXN];
std::vector <int> end[MAXN];

int f(int pos, int letter)
{
    if (bl[pos][letter])
    {
        return dp[pos][letter];
    }

    int cntOne = 0;
    int cntTwo = 0;
    bl[pos][letter] = true;
    dp[pos][letter] = 1;

    for (int i = pos ; i < n ; ++i)
    {
        for (const int &j : begin[i])
        {
            cntOne += (type[j] == 1);
            cntTwo += (type[j] == 2);
        }

        for (const int &j : end[i])
        {
            if (l[j] < pos)
            {
                continue;
            }

            cntOne -= (type[j] == 1);
            cntTwo -= (type[j] == 2);
        }

        if (cntOne == 0)
        {
            for (int j = letter + 1 ; j < 26 ; ++j)
            {
                dp[pos][letter] += f(i + 1, j);
                if (dp[pos][letter] >= MOD) dp[pos][letter] -= MOD;
            }
        }

        if (cntTwo == 0)
        {
            for (int j = letter - 1 ; j >= 0 ; --j)
            {
                dp[pos][letter] += f(i + 1, j);
                if (dp[pos][letter] >= MOD) dp[pos][letter] -= MOD;
            }
        }
    }

    return dp[pos][letter];
}

void solve()
{
    int sum = 0;
    for (int i = 0 ; i < 26 ; ++i)
    {
        sum += f(1, i);
        if (sum >= MOD) sum -= MOD;
    }

    std::cout << sum << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> l[i] >> r[i];
        type[i] = 1;

        if (l[i] > r[i])
        {
            std::swap(l[i], r[i]);
            type[i] = 2;
        }

        begin[l[i]].push_back(i);
        end[r[i]].push_back(i);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33468 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33412 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33368 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 6 ms 33372 KB Output is correct
13 Correct 6 ms 33428 KB Output is correct
14 Correct 6 ms 33372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33468 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33412 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33368 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 6 ms 33372 KB Output is correct
13 Correct 6 ms 33428 KB Output is correct
14 Correct 6 ms 33372 KB Output is correct
15 Correct 25 ms 33492 KB Output is correct
16 Correct 11 ms 33372 KB Output is correct
17 Correct 8 ms 33468 KB Output is correct
18 Correct 6 ms 33372 KB Output is correct
19 Correct 7 ms 33456 KB Output is correct
20 Correct 7 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Correct 8 ms 33628 KB Output is correct
23 Correct 28 ms 33368 KB Output is correct
24 Correct 7 ms 33372 KB Output is correct
25 Correct 8 ms 33372 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 6 ms 33468 KB Output is correct
3 Correct 7 ms 33456 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Execution timed out 4080 ms 80336 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33468 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33412 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33368 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 6 ms 33372 KB Output is correct
13 Correct 6 ms 33428 KB Output is correct
14 Correct 6 ms 33372 KB Output is correct
15 Correct 25 ms 33492 KB Output is correct
16 Correct 11 ms 33372 KB Output is correct
17 Correct 8 ms 33468 KB Output is correct
18 Correct 6 ms 33372 KB Output is correct
19 Correct 7 ms 33456 KB Output is correct
20 Correct 7 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Correct 8 ms 33628 KB Output is correct
23 Correct 28 ms 33368 KB Output is correct
24 Correct 7 ms 33372 KB Output is correct
25 Correct 8 ms 33372 KB Output is correct
26 Execution timed out 4045 ms 39324 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 6 ms 33468 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33412 KB Output is correct
6 Correct 6 ms 33372 KB Output is correct
7 Correct 6 ms 33372 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33368 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 6 ms 33372 KB Output is correct
13 Correct 6 ms 33428 KB Output is correct
14 Correct 6 ms 33372 KB Output is correct
15 Correct 25 ms 33492 KB Output is correct
16 Correct 11 ms 33372 KB Output is correct
17 Correct 8 ms 33468 KB Output is correct
18 Correct 6 ms 33372 KB Output is correct
19 Correct 7 ms 33456 KB Output is correct
20 Correct 7 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Correct 8 ms 33628 KB Output is correct
23 Correct 28 ms 33368 KB Output is correct
24 Correct 7 ms 33372 KB Output is correct
25 Correct 8 ms 33372 KB Output is correct
26 Correct 6 ms 33372 KB Output is correct
27 Correct 6 ms 33468 KB Output is correct
28 Correct 7 ms 33456 KB Output is correct
29 Correct 6 ms 33372 KB Output is correct
30 Execution timed out 4080 ms 80336 KB Time limit exceeded
31 Halted 0 ms 0 KB -