Submission #794638

#	Time	Username	Problem	Language	Result	Execution time	Memory
794638		phoenix	Misspelling (JOI22_misspelling)	C++17	100 / 100	3034 ms	253608 KiB

misspelling

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 500010;
const int MOD = 1e9 + 7;



int n, m;
ll dp[N][26];
ll pre[N][26];

vector<pair<int, int>> op[N];
vector<int> scan(vector<pair<int, int>> segs) {
    int m = (int)segs.size();
    // first = type, second = index
    for(int i = 0; i < m; i++) {
        op[segs[i].first].push_back({+1, i});
        op[segs[i].second].push_back({-1, i});
    }
    multiset<int> st;
    vector<int> res(n + 1);
    for(int i = 1; i <= n; i++) {
        for(auto [type, inx] : op[i]) {
            if(type == -1) {
                st.erase(st.find(segs[inx].first));
            } else {
                st.insert(segs[inx].first);
            }
        }
        res[i] = (st.empty() ? 0 : *(--st.end()));
    }
    for(int i = 0; i < m; i++) 
        op[segs[i].first].clear(),
        op[segs[i].second].clear();
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    vector<pair<int, int>> v[2];
    vector<int> grt(n + 1), sml(n + 1);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if(a < b) {
            v[0].push_back({a, b});
        } else {
            v[1].push_back({b, a});
        }
    }
    grt = scan(v[0]); sml = scan(v[1]);
    for(int c = 0; c < 26; c++) 
        dp[1][c] = pre[1][c] = 1;
    for(int i = 2; i <= n; i++) {
        for(int c = 0; c < 26; c++) {
            for(int d = 0; d < 26; d++) {
                if(d == c) continue;
                dp[i][c] += (pre[i - 1][d] - pre[max(grt[i - 1], sml[i - 1])][d] + MOD) % MOD;
                dp[i][c] %= MOD;
                if(sml[i - 1] < grt[i - 1]) {
                    if(d > c) 
                        dp[i][c] += (pre[grt[i - 1]][d] - pre[sml[i - 1]][d] + MOD) % MOD;
                } else {
                    if(d < c)
                        dp[i][c] += (pre[sml[i - 1]][d] - pre[grt[i - 1]][d] + MOD) % MOD;
                }
                dp[i][c] %= MOD;
            }
            pre[i][c] = (pre[i - 1][c] + dp[i][c]) % MOD;
        }
    }
    ll ans = 0;
    for(int c = 0; c < 26; c++) 
        ans = (ans + pre[n][c]) % MOD;
    cout << ans;
}

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