Submission #573788

#	Time	Username	Problem	Language	Result	Execution time	Memory
573788		InternetPerson10	Misspelling (JOI22_misspelling)	C++17	89 / 100	4054 ms	27728 KiB

misspelling

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int MOD = 1e9 + 7;

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

struct pairhash {
    size_t operator()(pair<int, int> const& p) const noexcept {
        return (hash<int>{}(p.first)) * 100 + hash<int>{}(p.second);
    }
};

vector<vector<pair<int, int>>> ops;
unordered_map<pair<int, int>, s, pairhash> ma, ma2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; 
    cin >> n >> m;
    pair<int, int> pee = {-1, -1};
    for(int i = 0; i < 26; i++) {
        ma[pee].ans[i] = 1;
    }
    ops.resize(n);
    for(int z = 0; z < m; z++) {
        int x, y;
        cin >> x >> y;
        if(x < y) {
            ops[x].push_back({y, 1});
        }
        else {
            ops[y].push_back({x, -1});
        }
    }
    for(int i = 1; i < n; i++) {
        for(auto pa : ma) {
            s ss;
            pair<int, int> p;
            tie(p, ss) = pa;
            for(auto pp : ops[i]) {
                if(pp.second == -1) {
                    p.first = max(p.first, pp.first);
                }
                else {
                    p.second = max(p.second, pp.first);
                }
            }
            if(p.first == i) p.first = -1;
            if(p.second == i) p.second = -1;
            if(p.first == -1) {
                int sum = 0;
                for(int i = 25; i >= 0; i--) {
                    sum += ss.ans[i];
                    sum %= MOD;
                    if(i) ma2[pee].ans[i-1] += sum;
                    if(i) ma2[pee].ans[i-1] %= MOD;
                }
            }
            if(p.second == -1) {
                int sum = 0;
                for(int i = 0; i < 26; i++) {
                    sum += ss.ans[i];
                    sum %= MOD;
                    if(i != 25) ma2[pee].ans[i+1] += sum;
                    if(i != 25) ma2[pee].ans[i+1] %= MOD;
                }
            }
            for(int i = 0; i < 26; i++) {
                ma2[p].ans[i] += ss.ans[i];
                ma2[p].ans[i] %= MOD;
            }
        }
        unordered_map<pair<int, int>, s, pairhash>().swap(ma);
        swap(ma, ma2);
    }
    int sum = 0;
    for(auto p : ma) {
        for(int i = 0; i < 26; i++) {
            sum += p.second.ans[i];
            sum %= MOD;
        }
    }
    cout << sum << '\n';
}

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