제출 #901674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901674		alexander707070	Misspelling (JOI22_misspelling)	C++14	100 / 100	1485 ms	116856 KiB

misspelling

#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;
 
const int mod=1e9+7;
 
int n,m,a,b,ans;
 
int dp[MAXN][30];
int es[MAXN],es2[MAXN];
bool bad[MAXN],bad2[MAXN];
int pt,pt2;

int sum[30],sum2[30];

set<int> s,t;
 
void calc_dp(){

    pt=pt2=n+1;

    for(int pos=n;pos>=1;pos--){

        auto it=s.lower_bound(pos+1);
        while(it!=s.end() and *it<=es[pos]){
            for(int letter=0;letter<26;letter++){
                sum[letter]-=dp[*it][letter]; sum[letter]+=mod; sum[letter]%=mod;
            }
            it++;
        }

        while(true){
            auto it=s.lower_bound(pos+1);
            if(it!=s.end() and *it<=es[pos])s.erase(it);
            else break;
        }

        it=t.lower_bound(pos+1);
        while(it!=t.end() and *it<=es2[pos]){
            for(int letter=0;letter<26;letter++){
                sum2[letter]-=dp[*it][letter]; sum2[letter]+=mod; sum2[letter]%=mod;
            }
            it++;
        }

        while(true){
            auto it=t.lower_bound(pos+1);
            if(it!=t.end() and *it<=es2[pos])t.erase(it);
            else break;
        }

        if(es[pos]>=pos+1)pt=pos+1;
        if(es2[pos]>=pos+1)pt2=pos+1;

        for(int letter=0;letter<26;letter++){

            dp[pos][letter]=1;
            
            for(int nxtletter=0;nxtletter<26;nxtletter++){
                if(nxtletter==letter)continue;
                
                if(nxtletter<letter)dp[pos][letter]+=sum[nxtletter];
                if(nxtletter>letter)dp[pos][letter]+=sum2[nxtletter];
                dp[pos][letter]%=mod;

            }
        }

        for(int letter=0;letter<26;letter++){
            sum[letter]+=dp[pos][letter]; sum[letter]%=mod;
            sum2[letter]+=dp[pos][letter]; sum2[letter]%=mod;
        }
    }
}
 
 
int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
 
        if(a<b){
            es[a]=max(es[a],b);
        }else{
            es2[b]=max(es2[b],a);
        }
    }

    for(int i=1;i<=n;i++){
        s.insert(i);
        t.insert(i);
    }

    calc_dp();
    for(int i=0;i<26;i++){
        ans+=dp[1][i];
        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