제출 #992563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992563		snpmrnhlol	Misspelling (JOI22_misspelling)	C++17	100 / 100	256 ms	160852 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5;
const int F = 26;
const int mod = 1e9 + 7;
const int inf = 2e9;
int ans = 0;
int v[N][2];
int v2[N][F][2];
int v3[N][2];
int s[F][2];
int cnt[2];
int dp[N][F];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 0;i < n;i++){
        v[i][0] = -1;
        v[i][1] = -1;
    }
    for(int i = 0;i < m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        if(a == b)continue;
        if(a < b){
            v[a][0] = max(v[a][0],b);
        }else{
            v[b][1] = max(v[b][1],a);
        }
    }
    for(int j = 0;j < F;j++){
        dp[n - 1][j] = 1;
    }
    for(int i = n - 2;i >= 0;i--){
        for(int k = 0;k < 2;k++){
            if(k == 0){
                for(int j = 1;j < F;j++){
                    v2[cnt[k]][j][k] = (s[j - 1][0] + s[j - 1][1] + 1)%mod;
                    if(v2[cnt[k]][j][k] >= mod)v2[cnt[k]][j][k]-=mod;
                }
            }else{
                for(int j = 0;j < F - 1;j++){
                    v2[cnt[k]][j][k] = (s[j + 1][0] + s[j + 1][1] + 1);
                    if(v2[cnt[k]][j][k] >= mod)v2[cnt[k]][j][k]-=mod;
                }
            }
            v3[cnt[k]][k] = i;
            cnt[k]++;
            if(k == 0){
                for(int j = 1;j < F;j++){
                    v2[cnt[0] - 1][j][0]+=v2[cnt[0] - 1][j - 1][0];
                    if(v2[cnt[0] - 1][j][0] >= mod)v2[cnt[0] - 1][j][0]-=mod;
                }
            }else{
                for(int j = F - 2;j >= 0;j--){
                    v2[cnt[1] - 1][j][1]+=v2[cnt[1] - 1][j + 1][1];
                    if(v2[cnt[1] - 1][j][1] >= mod)v2[cnt[1] - 1][j][1]-=mod;
                }
            }
        }
        for(int j = 0;j < F;j++){
            for(int k = 0;k < 2;k++){
                s[j][k]+=v2[cnt[k] - 1][j][k];
                s[j][k]%=mod;
            }
        }
        for(int k = 0;k < 2;k++){
            if(v[i][k] != -1){
                while(cnt[k] > 0 && v3[cnt[k] - 1][k] < v[i][k]){
                    for(int j = 0;j < F;j++){
                        s[j][k]-=v2[cnt[k] - 1][j][k];
                        if(s[j][k] < 0)s[j][k]+=mod;
                    }
                    cnt[k]--;
                }
            }
        }
        for(int j = 0;j < F;j++){
            for(int k = 0;k < 2;k++){
                dp[i][j]+=s[j][k];
                if(dp[i][j] >= mod)dp[i][j]-=mod;
            }
            dp[i][j]++;
        }
    }
    for(int j = 0;j < F;j++){
        ans+=dp[0][j];
        ans%=mod;
    }
    cout<<ans;
    return 0;
}

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