Submission #1248199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248199		Aviansh	Misspelling (JOI22_misspelling)	C++20	100 / 100	362 ms	105584 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int dp[n][26];
    vector<array<int,2>>constraints[n];
    for(int i = 0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        if(a==b)
            continue;
        if(a<b){
            constraints[a].push_back({b,1});
        }
        else{
            constraints[b].push_back({a,-1});
        }
    }
    for(int c = 0;c<26;c++){
        dp[n-1][c]=1;
    }
    set<int>pos1;
    set<int>pos2;
    pos1.insert(n-1);
    pos2.insert(n-1);
    int sum1[26];
    fill(sum1,sum1+26,1);
    int sum2[26];
    fill(sum2,sum2+26,1);
    //1 means 1, 2 means -1
    for(int i = n-2;i>=0;i--){
        for(array<int,2>cond : constraints[i]){
            if(cond[1]==1){
                while(pos1.size()&&*pos1.begin()<=cond[0]){
                    int a = *pos1.begin();
                    for(int j = 0;j<26;j++){
                        sum1[j]-=dp[a][j];
                        sum1[j]%=mod;
                    }
                    pos1.erase(pos1.begin());
                }
            }
            else{
                while(pos2.size()&&*pos2.begin()<=cond[0]){
                    int a = *pos2.begin();
                    for(int j = 0;j<26;j++){
                        sum2[j]-=dp[a][j];
                        sum2[j]%=mod;
                    }
                    pos2.erase(pos2.begin());
                }
            }
        }
        for(int j = 0;j<26;j++){
            dp[i][j]=1;
        }
        int pref = 0;
        for(int j = 0;j<25;j++){
            pref+=sum2[j];
            pref%=mod;
            dp[i][j+1]+=pref;
            dp[i][j+1]%=mod;
        }
        pref=0;
        for(int j = 25;j>0;j--){
            pref+=sum1[j];
            pref%=mod;
            dp[i][j-1]+=pref;
            dp[i][j-1]%=mod;
        }
        pos1.insert(i);
        pos2.insert(i);
        for(int j = 0;j<26;j++){
            sum1[j]+=dp[i][j];
            sum2[j]+=dp[i][j];
            sum1[j]%=mod;
            sum2[j]%=mod;
        }
    }
    int ans = 0;
    for(int i = 0;i<26;i++){
        ans+=dp[0][i];
        ans%=mod;
    }
    ans+=mod;
    ans%=mod;
    cout << ans << "\n";
    return 0;
}

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