Submission #892338

#	Time	Username	Problem	Language	Result	Execution time	Memory
892338		dimashhh	Misspelling (JOI22_misspelling)	C++17	100 / 100	310 ms	144720 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 1e9 + 7;
typedef long long ll;
int n,m,mx_x[N],mx_y[N];
ll dp[N][26],sum[26],ss[26];
set<int> st,st1;
void test(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        if(a < b){
            mx_x[a + 1] = max(mx_x[a + 1],b);
        }else{
            mx_y[b + 1] = max(mx_y[b + 1],a);
        }
    }
    for(int i = 0;i < 26;i++){
        dp[n][i] = 1;
        sum[i] = ss[i] = 1;
    }
    st.insert(n);
    st1.insert(n);
    for(int i = n - 1;i >= 1;i--){
        if(mx_y[i + 1] >= i + 1){
            while(!st.empty()){
                auto it = st.lower_bound(i + 1);
                if(it != st.end() && (*it) <= mx_y[i + 1]){
                    for(int c = 0;c < 26;c++){
                        sum[c] = (sum[c] - dp[*it][c]);
                        if(sum[c] < 0) sum[c] += MOD;
                    }
                    st.erase(it);
                }else break;
            }
        }
        if(mx_x[i + 1] >= i + 1){
            while(!st1.empty()){
                auto it = st1.lower_bound(i + 1);
                if(it != st.end() && (*it) <= mx_x[i + 1]){
                    for(int c = 0;c < 26;c++){
                        ss[c] = (ss[c] - dp[*it][c]);
                        if(ss[c] < 0) ss[c] += MOD;
                    }
                    st1.erase(it);
                }else break;
            }
        }
        for(int c =0 ;c < 26;c++){
            dp[i][c] = 1;
        }
        ll f = 0;
        for(int c = 1;c < 26;c++){
            f += sum[c - 1];
            if(f >= MOD) f -= MOD;
            dp[i][c] += f;
            if(dp[i][c] >= MOD) dp[i][c] -= MOD;
        }
        f = 0;
        for(int c = 25;c >=0;c--){
            f += ss[c + 1];
            if(f >= MOD) f -= MOD;
            dp[i][c] += f;
            if(dp[i][c] >= MOD) dp[i][c] -= MOD;
        }
        // for(int c = 0;c < 26;c++){
        //     dp[i][c] = 1;
        //     int x = 0,y = 0;
        //     for(int j = i + 1;j <= n;j++){
        //         x = max(x,mx_x[j]);
        //         y = max(y,mx_y[j]);
        //         for(int d = 0;d < 26;d++){
        //             if(d == c) continue;
        //             bool ok = false;
        //             if(d > c){
        //                 if(x < j){
        //                     ok = 1;
        //                 }
        //             }else{
        //                 if(y < j){
        //                     ok = 1;
        //                 }
        //             }
        //             if(ok){
        //                 dp[i][c] += dp[j][d];
        //                 ss[i] += dp[j][d];
        //                 if(dp[i][c] >= MOD) dp[i][c] -= MOD;
        //                 if(ss[i] >= MOD) ss[i] -= MOD;
        //             }
        //         }
        //     }
        // }
        st.insert(i);
        st1.insert(i);
        for(int c = 0;c < 26;c++){
            sum[c] += dp[i][c];
            if(sum[c] >= MOD) sum[c] -= MOD;
            ss[c] += dp[i][c];
            if(ss[c] >= MOD) ss[c] -= MOD;
        }
    }
    int ans = 0;
    for(int i = 0;i < 26;i++){
        ans +=  dp[1][i];
        if(ans>= MOD) ans -= MOD;
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        test();
}

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