제출 #1285951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285951		duckindog	Misspelling (JOI22_misspelling)	C++20	100 / 100	339 ms	96164 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

const int N = 500'000 + 10,
            M = 1'000'000'007;
int n, m;
pair<int, int> p[N];

vector<int> saveG[N], saveS[N];

int f[N][26];
inline void add(auto& x, const auto& y) { 
    x += y;
    if (x >= M) x -= M;
}

int pref[26], suff[26];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> p[i].first >> p[i].second;

    for (int i = 1; i <= m; ++i) { 
        const auto& [a, b] = p[i];
        if (a < b) saveG[a + 1].push_back(b);
        else saveS[b + 1].push_back(a);
    }

    set<int> sG, sS;
    fill(f[n], f[n] + 26, 1);
    for (int i = n - 1; i >= 1; --i) { 
        { // add suff
            int total = 0;
            for (int c = 25; c >= 0; --c) { 
                add(total, f[i + 1][c]);
                add(suff[c], total);
            }
            sG.insert(i + 1);
        }
        { // add pref
            int total = 0;
            for (int c = 0; c < 26; ++c) { 
                add(total, f[i + 1][c]);
                add(pref[c], total);
            }
            sS.insert(i + 1);
        }

        { // I + 1 -> R -1 req
            for (const auto& r : saveS[i + 1]) { 
                auto it = sG.lower_bound(i + 1);
                while (it != sG.end() && *it <= r) { 
                    { // del suff
                        int total = 0;
                        for (int c = 25; c >= 0; --c) { 
                            add(total, f[*it][c]);
                            add(suff[c], M - total);
                        }
                    }
                    it = sG.erase(it);
                }
            }
        }
        { // I + 1 -> R 1 req
            for (const auto& r : saveG[i + 1]) { 
                auto it = sS.lower_bound(i + 1);
                while (it != sS.end() && *it <= r) { 
                    { // del pref
                        int total = 0;
                        for (int c = 0; c < 26; ++c) { 
                            add(total, f[*it][c]);
                            add(pref[c], M - total);
                        }
                    }
                    it = sS.erase(it);
                }
            }
        }

        for (int c = 0; c < 26; ++c) { 
            auto& ret = f[i][c];
            add(ret, 1);
            if (c + 1 < 26) add(ret, suff[c + 1]);
            if (c - 1 >= 0) add(ret, pref[c - 1]);
        }
    }

    int answer = 0;
    for (int c = 0; c < 26; ++c) add(answer, f[1][c]);
    cout << answer << "\n";
}

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