Submission #1155669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155669		antonn	Misspelling (JOI22_misspelling)	C++20	100 / 100	3596 ms	875328 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 sum_pref[N][27][3], sum_suff[N][27][3];

struct SparseTable {
    vector<vector<int>> rmq;
    vector<int> lg;
    
    void init(int n, int a[]) {
        lg.resize(n + 1);
        for (int i = 2; i <= n; ++i) {
            lg[i] = lg[i / 2] + 1;
        }
        
        rmq.assign(20, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            rmq[0][i] = a[i];
        }
        for (int h = 1; h < 20; ++h) {
            for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
                rmq[h][i] = max(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
            }
        }
    }
    
    int get(int l, int r) {
        int p = lg[r - l + 1];
        return max(rmq[p][l], rmq[p][r - (1 << p) + 1]); 
    }
};

SparseTable s1, s2;

pair<bool, bool> sg(int l, int r) {
    bool s = (s1.get(l, r) > r);
    bool g = (s2.get(l, r) > r);
    return make_pair(s, g);
}

int get_pref(int l, int r, int k, int state) {
    if (l == 0) return sum_pref[r][k][state];
    return add(sum_pref[r][k][state], -sum_pref[l - 1][k][state]);
} 

int get_suff(int l, int r, int k, int state) {
    if (l == 0) return sum_suff[r][k][state];
    return add(sum_suff[r][k][state], -sum_suff[l - 1][k][state]);
} 

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);
        }
    }
    s1.init(n, mx_sm);
    s2.init(n, mx_gt);
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k < 26; ++k) {
            pair<bool, bool> state = {0, 0};
            int j = i;
            while (j >= 1) {
                state = sg(j, i);
                int l = 2, r = j, sol = 1;
                while (l <= r) {
                    int m = (l + r) / 2;
                    if (sg(m, i) == state) {
                        sol = m;
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                }
                
                int L = sol, R = j;
                
                bool s = state.first, g = state.second;
                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);
                    }
                    j = L - 1;
                    break;
                }
                
                if (s == 0 && g == 0) {
                    if (k > 0) addup(dp[i][k][NOTHING], get_pref(L - 1, R - 1, k - 1, BIGGER));
                    if (k > 0) addup(dp[i][k][NOTHING], get_pref(L - 1, R - 1, k - 1, NOTHING));
                    
                    addup(dp[i][k][NOTHING], get_suff(L - 1, R - 1, k + 1, SMALLER));
                    addup(dp[i][k][NOTHING], get_suff(L - 1, R - 1, k + 1, NOTHING));
                } else if (s == 1 && g == 0) {
                    if (k > 0) addup(dp[i][k][SMALLER], get_pref(L - 1, R - 1, k - 1, BIGGER));
                    if (k > 0) addup(dp[i][k][SMALLER], get_pref(L - 1, R - 1, k - 1, NOTHING));
                    
                    addup(dp[i][k][SMALLER], get_suff(L - 1, R - 1, k + 1, SMALLER));
                    addup(dp[i][k][SMALLER], get_suff(L - 1, R - 1, k + 1, NOTHING));
                } else if (s == 0 && g == 1) {
                    if (k > 0) addup(dp[i][k][BIGGER], get_pref(L - 1, R - 1, k - 1, BIGGER));
                    if (k > 0) addup(dp[i][k][BIGGER], get_pref(L - 1, R - 1, k - 1, NOTHING));
                    
                    addup(dp[i][k][BIGGER], get_suff(L - 1, R - 1, k + 1, SMALLER));
                    addup(dp[i][k][BIGGER], get_suff(L - 1, R - 1, k + 1, NOTHING));
                }
                j = L - 1;
            }
        }
        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]);
        }
        
        for (int k = 0; k < 26; ++k) {
            for (int state = 0; state < 3; ++state) {
                sum_pref[i][k][state] = add(sum_pref[i - 1][k][state], pref[i][k][state]);
            }
        }
        for (int k = 0; k < 26; ++k) {
            for (int state = 0; state < 3; ++state) {
                sum_suff[i][k][state] = add(sum_suff[i - 1][k][state], suff[i][k][state]);
            }
        }
    }
    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: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11