Submission #1114399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114399		ttamx	Misspelling (JOI22_misspelling)	C++17	100 / 100	2462 ms	66880 KiB

misspelling

#include<bits/stdc++.h>
 
using namespace std;
 
const int L=26;
const int N=5e5+5;
const int MOD=1e9+7;

int n,m;
int dp[N][L];
vector<pair<int,int>> a[2];
int pre[N][2];

int norm(int x){
    if(x<0)x+=MOD;
    if(x>=MOD)x-=MOD;
    return x;
}
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int l,r;
        cin >> l >> r;
        a[l>r].emplace_back(max(l,r),min(l,r));
    }
    for(int t=0;t<2;t++){
        sort(a[t].begin(),a[t].end());
        priority_queue<int> pq;
        pq.emplace(0);
        for(int i=n;i>=1;i--){
            while(!a[t].empty()&&a[t].back().first>=i){
                pq.emplace(a[t].back().second);
                a[t].pop_back();
            }
            while(pq.top()>=i){
                pq.pop();
            }
            pre[i][t]=pq.top();
        }
    }
    for(int i=0;i<26;i++){
        dp[1][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<26;j++){
            dp[i][j]=dp[i-1][j];
            for(int k=0;k<26;k++){
                if(j==k)continue;
                int s=j<k;
                dp[i][j]=norm(norm(dp[i][j]+dp[i-1][k])-dp[pre[i][s]][k]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<26;i++){
        ans=norm(ans+dp[n][i])%MOD;
    }
    cout << ans;
}

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