Submission #1120115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120115		12345678	Misspelling (JOI22_misspelling)	C++17	100 / 100	566 ms	61864 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5, kx=26, mod=1e9+7;

int n, m, a, b, dp[nx][kx], res, up[nx], dn[nx], qsup[nx], qsdn[nx];
stack<int> cu, cd;

void calcup(int idx, int mul)
{
    int tmp=0;
    for (int i=25; i>=0; i--)
    {
        tmp=((tmp+dp[idx][i]*mul)%mod+mod)%mod;
        qsup[i]=(qsup[i]+tmp)%mod;
    }
}

void calcdn(int idx, int mul)
{
    //cout<<"calcdn "<<idx<<' '<<mul<<'\n';
    int tmp=0;
    for (int i=0; i<26; i++)
    {
        tmp=((tmp+dp[idx][i]*mul)%mod+mod)%mod;
        qsdn[i]=(qsdn[i]+tmp)%mod;
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>a>>b;
        if (a<b) dn[a+1]=max(dn[a+1], b);
        else up[b+1]=max(up[b+1], a);
    }
    for (int i=n; i>=1; i--)
    {
        for (int c=0; c<26; c++)
        {
            dp[i][c]=1;
            if (c>0) dp[i][c]=(dp[i][c]+qsdn[c-1])%mod;
            if (c<25) dp[i][c]=(dp[i][c]+qsup[c+1])%mod;
            //cout<<"debug "<<i<<' '<<c<<' '<<dp[i][c]<<'\n';
        }
        cu.push(i);
        calcup(i, 1);
        cd.push(i);
        calcdn(i, 1);
        while (!cd.empty()&&cd.top()<=up[i]) calcdn(cd.top(), -1), cd.pop();
        while (!cu.empty()&&cu.top()<=dn[i]) calcup(cu.top(), -1), cu.pop();
    }
    for (int c=0; c<26; c++) res=(res+dp[1][c])%mod;
    cout<<res;
}

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