제출 #922600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922600		esomer	Misspelling (JOI22_misspelling)	C++17	100 / 100	1374 ms	167504 KiB

misspelling

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

const int MOD = 1e9 + 7;

#define int long long

int sum(int l, int r, vector<int>& pre){
    if(l > r) return 0;
    if(l > 0) return (pre[r] - pre[l-1] + MOD) % MOD;
    else return pre[r];
}

void solve(){
    int n, m; cin >> n >> m;
    vector<pair<vector<int>, vector<int>>> ends(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--; b--;
        int type = 1;
        if(a > b) {type = 2; swap(a, b);}
        a++;
        if(type == 1) ends[b].first.push_back(a); //In type 1, i is >= than i + 1.
        else ends[b].second.push_back(a); //In type 2, i is <= than i + 1.
        // cout << "i "<< i << " type "<< type << " a "<< a << " b "<< b << "\n";
    }
    vector<pair<int, int>> mx(n, {0, 0});
    pair<set<int>, set<int>> curr; curr.first.insert(0); curr.second.insert(0);
    for(int i = n - 1; i >= 0; i--){
        curr.first.erase(i+1);
        curr.second.erase(i+1);
        for(int& y : ends[i].first) curr.first.insert(y);
        for(int& y : ends[i].second) curr.second.insert(y);
        mx[i].first = *curr.first.rbegin();
        mx[i].second = *curr.second.rbegin();
    }
    vector<vector<int>> prefix(26, vector<int>(n, 0));
    for(int i = 0; i < 26; i++) prefix[i][0] = 1;
    for(int i = 1; i < n; i++){
        // cout << "i "<< i << " mx "<< mx[i].first << " "<< mx[i].second << "\n";
        vector<int> dp(26, 0);
        for(int j = 0; j < 26; j++){
            for(int q = 0; q < 26; q++){
                if(q == j) continue;
                if(q < j){
                    dp[q] = (dp[q] + sum(mx[i].second, i-1, prefix[j])) % MOD;
                }else{
                    dp[q] = (dp[q] + sum(mx[i].first, i-1, prefix[j])) % MOD;
                }
            }
        }
        for(int j = 0; j < 26; j++){
            prefix[j][i] = (prefix[j][i-1] + dp[j]) % MOD;
        }
        // cout << "i "<< i << endl;
        // for(int j = 0; j < 26; j++){
        //     cout << "j "<< j << " dp " << dp[j] << "\n";
        // }
    }
    int ans = 0;
    for(int i = 0; i < 26; i++) ans = (ans + sum(0, n-1, prefix[i])) % MOD;
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
    return 0;
}

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