제출 #1155654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155654		antonn	Misspelling (JOI22_misspelling)	C++20	28 / 100	4110 ms	474024 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 1e9 + 7;

int add(int a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
    return a;
}

void addup(int &a, int b) {
    a = add(a, b);
}

const int N = 5e5 + 7;
const int SMALLER = 0;
const int BIGGER = 1;
const int NOTHING = 2;

int mx_sm[N], mx_gt[N];
int dp[N][26][3], pref[N][27][3], suff[N][27][3]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        if (a <= b) {
            mx_sm[a] = max(mx_sm[a], b);
        } else {
            mx_gt[b] = max(mx_gt[b], a);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < 26; ++k) {
            bool s = 0, g = 0;
            for (int j = i; j >= 1; --j) {
                if (mx_sm[j] > i) s = 1;
                if (mx_gt[j] > i) g = 1;
                
                if (s == 1 && g == 1) break;
                
                if (j == 1) {
                    if (s == 0 && g == 0) {
                        addup(dp[i][k][NOTHING], 1);
                    } else if (s == 1 && g == 0) {
                        addup(dp[i][k][SMALLER], 1);
                    } else if (s == 0 && g == 1) {
                        addup(dp[i][k][BIGGER], 1);
                    }
                    continue;
                }
                
                if (s == 0 && g == 0) {
                    if (k > 0) addup(dp[i][k][NOTHING], pref[j - 1][k - 1][BIGGER]);
                    if (k > 0) addup(dp[i][k][NOTHING], pref[j - 1][k - 1][NOTHING]);
                    
                    addup(dp[i][k][NOTHING], suff[j - 1][k + 1][SMALLER]);
                    addup(dp[i][k][NOTHING], suff[j - 1][k + 1][NOTHING]);
                } else if (s == 1 && g == 0) {
                    if (k > 0) addup(dp[i][k][SMALLER], pref[j - 1][k - 1][BIGGER]);
                    if (k > 0) addup(dp[i][k][SMALLER], pref[j - 1][k - 1][NOTHING]);
                    
                    addup(dp[i][k][SMALLER], suff[j - 1][k + 1][SMALLER]);
                    addup(dp[i][k][SMALLER], suff[j - 1][k + 1][NOTHING]);
                } else if (s == 0 && g == 1) {
                    if (k > 0) addup(dp[i][k][BIGGER], pref[j - 1][k - 1][BIGGER]);
                    if (k > 0) addup(dp[i][k][BIGGER], pref[j - 1][k - 1][NOTHING]);
                    
                    addup(dp[i][k][BIGGER], suff[j - 1][k + 1][SMALLER]);
                    addup(dp[i][k][BIGGER], suff[j - 1][k + 1][NOTHING]);
                }
            }
        }
        pref[i][0][SMALLER] = dp[i][0][SMALLER];
        pref[i][0][BIGGER] = dp[i][0][BIGGER];
        pref[i][0][NOTHING] = dp[i][0][NOTHING];
        for (int k = 1; k < 26; ++k) {
            pref[i][k][SMALLER] = add(pref[i][k - 1][SMALLER], dp[i][k][SMALLER]);
            pref[i][k][BIGGER] = add(pref[i][k - 1][BIGGER], dp[i][k][BIGGER]);
            pref[i][k][NOTHING] = add(pref[i][k - 1][NOTHING], dp[i][k][NOTHING]);
        }
        for (int k = 25; k >= 0; --k) {
            suff[i][k][SMALLER] = add(suff[i][k + 1][SMALLER], dp[i][k][SMALLER]);
            suff[i][k][BIGGER] = add(suff[i][k + 1][BIGGER], dp[i][k][BIGGER]);
            suff[i][k][NOTHING] = add(suff[i][k + 1][NOTHING], dp[i][k][NOTHING]);
        }
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) addup(ans, dp[n][i][NOTHING]);
    cout << ans << "\n";
    return 0;
}
/**
abcdefgh
  x  y
     
ab|def|gh
ab|cde|gh
**/

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