제출 #1006113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006113		Sharky	Misspelling (JOI22_misspelling)	C++17	100 / 100	1094 ms	262652 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+8;
const int M = 1e9+7;
int n, m, dp[N][27], ps[N][27], ans;
vector<pair<int, int>> req[N];
multiset<int> st[2];
signed main() {
    cin >> n >> m;
    while (m--) {
        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 = 1, k; s+1; s--) {
            auto it = st[s^1].lower_bound(i);
            if (it == st[s^1].begin()) k = 0;
            else k = *(--it);
            for (int j = 1; j <= 26; j++) {
                if (!s) (dp[i][j] += ((ps[i - 1][j - 1] - ps[k][j - 1] + M) % M)) %= M;
                else ((dp[i][j] += (ps[i - 1][26] - ps[i - 1][j] - ps[k][26] + ps[k][j] + M + M)) %= M);               
            }
        }
        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] + M) % M;
        for (auto [x, y] : req[i]) st[y].erase(st[y].find(x));
    }
    cout << ps[n][26];
}

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