Submission #1007527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007527		tosivanmak	Misspelling (JOI22_misspelling)	C++17	100 / 100	2468 ms	388020 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
ll canlare[500005][27],cansmale[500005][27],canall[500005][27];
multiset<ll>prevpos[2];
vector<ll>add[500005],remov[500005];
ll dpcanlare[27],dpcansmale[27],dpcanall[27];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll a[m+5],b[m+5];
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        ll mul=1;
        if(a[i]<b[i])mul*=(-1);
        add[min(a[i],b[i])].push_back(mul*min(a[i],b[i]));
        remov[max(a[i],b[i])].push_back(mul*min(a[i],b[i]));
    }
    for(int i=1;i<=26;i++){
        canall[0][i]=0;
    }
    for(int i=1;i<=n;i++){

        for(int j=1;j<=26;j++){dpcanlare[j]=dpcansmale[j]=dpcanall[j]=0;}
        // 0 = can only lar, 1 = can only small
        for(auto& u: add[i]){
            if(u<0)prevpos[0].insert(-u);
            else prevpos[1].insert(u);
        }
        for(auto& u: remov[i]){
            if(u<0)prevpos[0].erase(prevpos[0].find(-u));
            else prevpos[1].erase(prevpos[1].find(u));
        }
        if(prevpos[0].size()==0&&prevpos[1].size()==0){
            for(int j=1;j<=26;j++){
                dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]+1;
                dpcanall[j]%=MOD;
            }
        }
        else if(prevpos[0].size()==0){
            ll lol=*prevpos[1].rbegin();
            for(int j=1;j<=26;j++){
                dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]-(canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]);
                dpcansmale[j]=canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]+1;
                dpcanall[j]%=MOD,dpcansmale[j]%=MOD,dpcanlare[j]%=MOD;
            }
        }
        else if(prevpos[1].size()==0){
            ll lol=*prevpos[0].rbegin();
            for(int j=1;j<=26;j++){
                dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]-(canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]);
                dpcanlare[j]=canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]+1;
                dpcanall[j]%=MOD,dpcansmale[j]%=MOD,dpcanlare[j]%=MOD;
            }
        }
        else{
            ll lol=*prevpos[0].rbegin(),lol2=*prevpos[1].rbegin();
            for(int j=1;j<=26;j++){
                if(lol==lol2){
                    for(int j=1;j<=26;j++){
                        dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]-(canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]);
                        dpcanall[j]%=MOD,dpcansmale[j]%=MOD,dpcanlare[j]%=MOD;
                    }
                }
                else if(lol>lol2){
                    for(int j=1;j<=26;j++){
                        dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]-(canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]);
                        dpcanlare[j]=canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]-(canall[lol2-1][j-1]+canall[lol2-1][26]-canall[lol2-1][j]+canlare[lol2-1][j-1]+cansmale[lol2-1][26]-cansmale[lol2-1][j]);
                        dpcanall[j]%=MOD,dpcansmale[j]%=MOD,dpcanlare[j]%=MOD;
                    }
                }
                else{
                    for(int j=1;j<=26;j++){
                        dpcanall[j]=canall[i-1][j-1]+canall[i-1][26]-canall[i-1][j]+canlare[i-1][j-1]+cansmale[i-1][26]-cansmale[i-1][j]-(canall[lol2-1][j-1]+canall[lol2-1][26]-canall[lol2-1][j]+canlare[lol2-1][j-1]+cansmale[lol2-1][26]-cansmale[lol2-1][j]);
                        dpcansmale[j]=canall[lol2-1][j-1]+canall[lol2-1][26]-canall[lol2-1][j]+canlare[lol2-1][j-1]+cansmale[lol2-1][26]-cansmale[lol2-1][j]-(canall[lol-1][j-1]+canall[lol-1][26]-canall[lol-1][j]+canlare[lol-1][j-1]+cansmale[lol-1][26]-cansmale[lol-1][j]);
                        dpcanall[j]%=MOD,dpcansmale[j]%=MOD,dpcanlare[j]%=MOD;
                    }
                }
            }
        }
        for(int j=1;j<=26;j++){
            canall[i][j]=canall[i-1][j]+canall[i][j-1]-canall[i-1][j-1]+dpcanall[j];
            cansmale[i][j]=cansmale[i-1][j]+cansmale[i][j-1]-cansmale[i-1][j-1]+dpcansmale[j];
            canlare[i][j]=canlare[i-1][j]+canlare[i][j-1]-canlare[i-1][j-1]+dpcanlare[j];
            canall[i][j]%=MOD,cansmale[i][j]%=MOD,canlare[i][j]%=MOD;
        }
    }
    ll ans=canall[n][26]-canall[n-1][26];
    ans%=MOD;ans+=MOD;ans%=MOD;
    cout<<ans<<'\n';
}

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