oj.uz

Submission #793630

# Submission time Handle Problem Language Result Execution time Memory
793630 2023-07-26T04:53:20 Z vjudge1 Misspelling (JOI22_misspelling) C++17
100 / 100
 1457 ms 171344 KB 
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 500500;
const int mod = 1e9 + 7;

using namespace std;

void add(int &x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    } else if (x < 0) {
        x += mod;
    }
}

int n;
int m;
int d[N][26];
int s[N][26];
vector<int> A[N], B[N];

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (a == b) {
            continue;
        }

        if (a < b) {
            A[a].push_back(b);
        } else {
            B[b].push_back(a);
        }
    }

    for (int i = 0; i < 26; i++) {
        d[1][i] = s[1][i] = 1;
    }

    set<pair<int, int>> S, T;

    for (int i = 2; i <= n; i++) {
        for (int j: A[i - 1]) {
            S.insert({i - 1, j});
        }
        for (int j: B[i - 1]) {
            T.insert({i - 1, j});
        }
        while (!S.empty() && (--S.end())->se < i) {
            S.erase(--S.end());
        }
        while (!T.empty() && (--T.end())->se < i) {
            T.erase(--T.end());
        }
        int p_1 = S.empty() ? 0 : (--S.end())->fi;
        int p_2 = T.empty() ? 0 : (--T.end())->fi;
        for (int j = 0; j < 26; j++) {
            for (int h = 0; h < j; h++) {
                add(d[i][j], s[i - 1][h] - s[max(p_1, p_2)][h]);
                if (p_1 < p_2) {
                    add(d[i][j], s[p_2][h] - s[p_1][h]);
                }
            }
            for (int h = j + 1; h < 26; h++) {
                add(d[i][j], s[i - 1][h] - s[max(p_1, p_2)][h]);
                if (p_1 > p_2) {
                    add(d[i][j], s[p_1][h] - s[p_2][h]);
                }
            }

            s[i][j] = s[i - 1][j];
            add(s[i][j], d[i][j]);
        }
    }

    int res = 0;
    for (int i = 0; i < 26; i++) {
        add(res, s[n][i]);
    }

    cout << res << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23832 KB Output is correct
4 Correct 12 ms 23748 KB Output is correct
5 Correct 12 ms 23832 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 10 ms 23764 KB Output is correct
9 Correct 12 ms 23836 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 10 ms 23832 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23832 KB Output is correct
4 Correct 12 ms 23748 KB Output is correct
5 Correct 12 ms 23832 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 10 ms 23764 KB Output is correct
9 Correct 12 ms 23836 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 10 ms 23832 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23840 KB Output is correct
15 Correct 12 ms 23836 KB Output is correct
16 Correct 10 ms 23764 KB Output is correct
17 Correct 12 ms 23836 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23840 KB Output is correct
20 Correct 12 ms 23832 KB Output is correct
21 Correct 12 ms 23804 KB Output is correct
22 Correct 16 ms 24364 KB Output is correct
23 Correct 14 ms 23756 KB Output is correct
24 Correct 12 ms 23848 KB Output is correct
25 Correct 14 ms 23844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23736 KB Output is correct
3 Correct 12 ms 23836 KB Output is correct
4 Correct 12 ms 23792 KB Output is correct
5 Correct 971 ms 165932 KB Output is correct
6 Correct 936 ms 165264 KB Output is correct
7 Correct 915 ms 166308 KB Output is correct
8 Correct 957 ms 168396 KB Output is correct
9 Correct 947 ms 166376 KB Output is correct
10 Correct 61 ms 29572 KB Output is correct
11 Correct 12 ms 23836 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 905 ms 171344 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23832 KB Output is correct
4 Correct 12 ms 23748 KB Output is correct
5 Correct 12 ms 23832 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 10 ms 23764 KB Output is correct
9 Correct 12 ms 23836 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 10 ms 23832 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23840 KB Output is correct
15 Correct 12 ms 23836 KB Output is correct
16 Correct 10 ms 23764 KB Output is correct
17 Correct 12 ms 23836 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23840 KB Output is correct
20 Correct 12 ms 23832 KB Output is correct
21 Correct 12 ms 23804 KB Output is correct
22 Correct 16 ms 24364 KB Output is correct
23 Correct 14 ms 23756 KB Output is correct
24 Correct 12 ms 23848 KB Output is correct
25 Correct 14 ms 23844 KB Output is correct
26 Correct 58 ms 29572 KB Output is correct
27 Correct 71 ms 28668 KB Output is correct
28 Correct 71 ms 28728 KB Output is correct
29 Correct 44 ms 29516 KB Output is correct
30 Correct 45 ms 29600 KB Output is correct
31 Correct 202 ms 59968 KB Output is correct
32 Correct 47 ms 29004 KB Output is correct
33 Correct 46 ms 29132 KB Output is correct
34 Correct 46 ms 29420 KB Output is correct
35 Correct 208 ms 60104 KB Output is correct
36 Correct 52 ms 27880 KB Output is correct
37 Correct 43 ms 29064 KB Output is correct
38 Correct 46 ms 28716 KB Output is correct
39 Correct 47 ms 28336 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 10 ms 23832 KB Output is correct
4 Correct 12 ms 23748 KB Output is correct
5 Correct 12 ms 23832 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 10 ms 23764 KB Output is correct
9 Correct 12 ms 23836 KB Output is correct
10 Correct 11 ms 23720 KB Output is correct
11 Correct 10 ms 23832 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23840 KB Output is correct
15 Correct 12 ms 23836 KB Output is correct
16 Correct 10 ms 23764 KB Output is correct
17 Correct 12 ms 23836 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23840 KB Output is correct
20 Correct 12 ms 23832 KB Output is correct
21 Correct 12 ms 23804 KB Output is correct
22 Correct 16 ms 24364 KB Output is correct
23 Correct 14 ms 23756 KB Output is correct
24 Correct 12 ms 23848 KB Output is correct
25 Correct 14 ms 23844 KB Output is correct
26 Correct 12 ms 23780 KB Output is correct
27 Correct 12 ms 23736 KB Output is correct
28 Correct 12 ms 23836 KB Output is correct
29 Correct 12 ms 23792 KB Output is correct
30 Correct 971 ms 165932 KB Output is correct
31 Correct 936 ms 165264 KB Output is correct
32 Correct 915 ms 166308 KB Output is correct
33 Correct 957 ms 168396 KB Output is correct
34 Correct 947 ms 166376 KB Output is correct
35 Correct 61 ms 29572 KB Output is correct
36 Correct 12 ms 23836 KB Output is correct
37 Correct 12 ms 23764 KB Output is correct
38 Correct 905 ms 171344 KB Output is correct
39 Correct 58 ms 29572 KB Output is correct
40 Correct 71 ms 28668 KB Output is correct
41 Correct 71 ms 28728 KB Output is correct
42 Correct 44 ms 29516 KB Output is correct
43 Correct 45 ms 29600 KB Output is correct
44 Correct 202 ms 59968 KB Output is correct
45 Correct 47 ms 29004 KB Output is correct
46 Correct 46 ms 29132 KB Output is correct
47 Correct 46 ms 29420 KB Output is correct
48 Correct 208 ms 60104 KB Output is correct
49 Correct 52 ms 27880 KB Output is correct
50 Correct 43 ms 29064 KB Output is correct
51 Correct 46 ms 28716 KB Output is correct
52 Correct 47 ms 28336 KB Output is correct
53 Correct 810 ms 148568 KB Output is correct
54 Correct 1457 ms 148432 KB Output is correct
55 Correct 863 ms 169504 KB Output is correct
56 Correct 894 ms 169692 KB Output is correct
57 Correct 925 ms 165852 KB Output is correct
58 Correct 904 ms 160428 KB Output is correct
59 Correct 897 ms 161968 KB Output is correct
60 Correct 947 ms 167136 KB Output is correct
61 Correct 1000 ms 125500 KB Output is correct
62 Correct 860 ms 157388 KB Output is correct
63 Correct 854 ms 147216 KB Output is correct
64 Correct 765 ms 136720 KB Output is correct