Submission #937094

#	Time	Username	Problem	Language	Result	Execution time	Memory
937094		Pannda	Misspelling (JOI22_misspelling)	C++17	100 / 100	573 ms	253076 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    static constexpr int P = 1e9 + 7;

    auto add = [](int &x, int y) {
        x += y;
        if (x >= P) x -= P;
        if (x < 0) x += P;
    };

    int n, m;
    cin >> n >> m;

    vector<int> enforce0(n, -1); // enforces s[i] >= s[i + 1]
    vector<int> enforce1(n, -1); // enforces s[i] <= s[i + 1]

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if (a < b) enforce0[a] = max(enforce0[a], b);
        else enforce1[b] = max(enforce1[b], a);
    }

    vector<int> all(n);
    iota(all.begin(), all.end(), 0);
    set<int> s0(all.begin(), all.end());
    set<int> s1(all.begin(), all.end());

    vector<vector<int>> dp(n, vector<int>(26, 0));
    vector<vector<int>> upper(n, vector<int>(26, 0));
    vector<vector<int>> lower(n, vector<int>(26, 0));
    dp[n - 1] = vector<int>(26, 1);
    int f = accumulate(dp[n - 1].begin(), dp[n - 1].end(), 0LL) % P;

    auto update = [&](int i) {
        for (int c = 24; c >= 0; c--) {
            upper[i][c] = upper[i][c + 1];
            add(upper[i][c], dp[i][c + 1]);
        }
        for (int c = 1; c < 26; c++) {
            lower[i][c] = lower[i][c - 1];
            add(lower[i][c], dp[i][c - 1]);
        }
    };
    update(n - 1);

    for (int i = n - 2; i >= 0; i--) {
        vector<int> adj0;
        vector<int> adj1;
        if (enforce0[i] != -1) {
            while (true) {
                auto it = s0.upper_bound(i);
                if (it == s0.end() || *it > enforce0[i]) break;
                adj0.push_back(*it);
                s0.erase(it);
            }
        }
        if (enforce1[i] != -1) {
            while (true) {
                auto it = s1.upper_bound(i);
                if (it == s1.end() || *it > enforce1[i]) break;
                adj1.push_back(*it);
                s1.erase(it);
            }
        }
        for (int c = 0; c < 26; c++) {
            add(dp[i][c], f);
            for (int j : adj0) {
                add(dp[i][c], -upper[j][c]);
            }
            for (int j : adj1) {
                add(dp[i][c], -lower[j][c]);
            }
        }
        update(i);
        f = accumulate(dp[i].begin(), dp[i].end(), 0LL) % P;
    }

    cout << f << '\n';
}

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