Submission #544701

#	Time	Username	Problem	Language	Result	Execution time	Memory
544701		kevinxiehk	Misspelling (JOI22_misspelling)	C++17	100 / 100	3193 ms	171476 KiB

misspelling

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;
int n, m;
int dp[500005][30];
vector<int> up[500005], down[500005];
priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> nowup, nowdown;
const int mod = 1000000007;
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    int l, r;
    for(int i = 0; i < m; i++) {
        cin >> l >> r;
        if(l < r) {
            down[l].pb(r);
        }
        else up[r].pb(l);
    }
    for(int i = 0; i <= 26; i++) {
        dp[1][i] = 1;
    }
    for(auto x: down[1]) {
        nowdown.push(mp(1, x));
    }
    for(auto x: up[1]) {
        nowup.push(mp(1, x));
    }
    for(int i = 2; i <= n; i++) {
        while(!nowup.empty() && nowup.top().se < i) nowup.pop();
        while(!nowdown.empty() && nowdown.top().se < i) nowdown.pop();

        for(int j = 0; j < 26; j++) dp[i][j] = dp[i - 1][j];
        
        if(nowup.empty() && nowdown.empty()) {
            for(int j = 0; j < 26; j++) {
                for(int k = 0; k < 26; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                    }
                }
            }
        }
        else if(nowup.empty()) {
            int lim = nowdown.top().fi;
            for(int j = 0; j < 26; j++) {
                for(int k = 0; k < 26; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k] - dp[lim][k] + mod) % mod;
                    }
                }
            }
            for(int j = 0; j < 26; j++) {
                for(int k = j + 1; k < 26; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[lim][k] + mod) % mod;
                    }
                }
            }
        }
        else if(nowdown.empty()){
            int lim = nowup.top().fi;
            for(int j = 0; j < 26; j++) {
                for(int k = 0; k < 26; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k] - dp[lim][k] + mod) % mod;
                    }
                }
            }
            for(int j = 0; j < 26; j++) {
                for(int k = 0; k < j; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[lim][k] + mod) % mod;
                    }
                }
            }
        }
        else {
            int limup = nowup.top().fi;
            int limdown = nowdown.top().fi;
            int lim = max(limup, limdown);
            for(int j = 0; j < 26; j++) {
                for(int k = 0; k < 26; k++) {
                    if(j != k) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k] - dp[lim][k] + mod) % mod;
                    }
                }
            }
            if(limup < limdown) {
                for(int j = 0; j < 26; j++) {
                    for(int k = j + 1; k < 26; k++) {
                        if(j != k) {
                            dp[i][j] = (dp[i][j] + dp[lim][k] - dp[limup][k] + mod) % mod;
                        }
                    }
                }
            }
            else {
                for(int j = 0; j < 26; j++) {
                    for(int k = 0; k < j; k++) {
                        if(j != k) {
                            dp[i][j] = (dp[i][j] + dp[lim][k] - dp[limdown][k] + mod) % mod;
                        }
                    }
                }
            }
        }

        for(auto x: down[i]) {
            nowdown.push(mp(i, x));
        }
        for(auto x: up[i]) {
            nowup.push(mp(i, x));
        }
    }

    int ans = 0;
    for(int i = 0; i < 26; i++) ans += dp[n][i];
    cout << ans % mod << '\n';
    return 0;
}

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