Submission #573789

#	Time	Username	Problem	Language	Result	Execution time	Memory
573789		InternetPerson10	Misspelling (JOI22_misspelling)	C++17	89 / 100	4081 ms	27724 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 (p.first ^ p.second ^ (p.first + 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