Submission #1155651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155651		antonn	Misspelling (JOI22_misspelling)	C++20	28 / 100	4099 ms	192028 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
}

const int N = 5e5 + 7;
const int SMALLER = 0;
const int BIGGER = 1;
const int NOTHING = 2;

vector<int> sm[N], gt[N];
int dp[N][26][3]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        if (a <= b) {
            sm[a].push_back(b);
        } else {
            gt[b].push_back(a);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < 26; ++k) {
            bool s = 0, g = 0;
            for (int j = i; j >= 1; --j) {
                for (auto x : sm[j]) {
                    if (x > i) s = 1;
                }
                for (auto x : gt[j]) {
                    if (x > i) g = 1;
                }
                if (s == 1 && g == 1) break;
                
                if (j == 1) {
                    if (s == 0 && g == 0) {
                        add(dp[i][k][NOTHING], 1);
                    } else if (s == 1 && g == 0) {
                        add(dp[i][k][SMALLER], 1);
                    } else if (s == 0 && g == 1) {
                        add(dp[i][k][BIGGER], 1);
                    }
                    continue;
                }
                for (int p = 0; p < 26; ++p) {
                    if (p == k) continue;
                    if (s == 0 && g == 0) {
                        if (p < k) {
                            add(dp[i][k][NOTHING], dp[j - 1][p][BIGGER]);
                            add(dp[i][k][NOTHING], dp[j - 1][p][NOTHING]);
                        } else {
                            add(dp[i][k][NOTHING], dp[j - 1][p][SMALLER]);
                            add(dp[i][k][NOTHING], dp[j - 1][p][NOTHING]);
                        }
                    } else if (s == 1 && g == 0) {
                        if (p < k) {
                            add(dp[i][k][SMALLER], dp[j - 1][p][BIGGER]);
                            add(dp[i][k][SMALLER], dp[j - 1][p][NOTHING]);
                        } else {
                            add(dp[i][k][SMALLER], dp[j - 1][p][SMALLER]);
                            add(dp[i][k][SMALLER], dp[j - 1][p][NOTHING]);
                        }
                    } else if (s == 0 && g == 1) {
                        if (p < k) {
                            add(dp[i][k][BIGGER], dp[j - 1][p][BIGGER]);
                            add(dp[i][k][BIGGER], dp[j - 1][p][NOTHING]);
                        } else {
                            add(dp[i][k][BIGGER], dp[j - 1][p][SMALLER]);
                            add(dp[i][k][BIGGER], dp[j - 1][p][NOTHING]);
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) add(ans, dp[n][i][NOTHING]);
    cout << ans << "\n";
    return 0;
}
/**
abcdefgh
  x  y
     
ab|def|gh
ab|cde|gh
**/

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