Submission #1006109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006109		Sharky	Misspelling (JOI22_misspelling)	C++17	100 / 100	1071 ms	269268 KiB

misspelling

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

#define int long long
const int N = 500008;
const int mod = 1e9 + 7;

int n, m, dp[N][27], ps[N][27], ans = 0;
vector<pair<int, int>> req[N];
multiset<int> st[2];

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        req[max(l, r)].push_back({min(l, r), (l < r) ? 1 : 0});
        if (l < r) st[1].insert(l);
        else st[0].insert(r);
    }
    for (int i = 1; i <= 26; i++) dp[1][i] = 1, ps[1][i] = i;
    for (int i = 2; i <= n; i++) {
        for (int s = 0; s <= 1; s++) {
            int k;
            auto it = st[s ^ 1].lower_bound(i);
            if (st[s ^ 1].empty() || it == st[s ^ 1].begin()) k = 1;
            else k = *(--it) + 1;
            for (int j = 1; j <= 26; j++) {
                if (!s) {
                    (dp[i][j] += ((ps[i - 1][j - 1] - ps[k - 1][j - 1] + mod) % mod)) %= mod;
                } else {
                    (dp[i][j] += (((ps[i - 1][26] - ps[i - 1][j]) - (ps[k - 1][26] - ps[k - 1][j]) + 2 * mod) % mod)) %= mod;               
                }
            }
        }
        for (int j = 1; j <= 26; j++) ps[i][j] = (ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + dp[i][j] + mod) % mod;
        for (auto& [x, y] : req[i]) st[y].erase(st[y].lower_bound(x));
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= 26; j++) (ans += dp[i][j]) %= mod;
    cout << ans << '\n';
}

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