Submission #1178333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178333		ace5	Misspelling (JOI22_misspelling)	C++20	100 / 100	283 ms	247088 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;
const int mod = 1000000007;
const int maxlog = 19;
const int alf = 26;

int add(int a,int b)
{
    return a+b >= mod ? a+b-mod : a+b;
}

vector<pair<int,int>> st1,stn;

int dp[2][alf][maxn],pref[alf+1][maxn],suf[alf+1][maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<vector<int>> r1(n),rn(n);
    for(int i = 0;i < m;++i)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        if(a < b)
        {
            rn[a].push_back(b-1);
        }
        else
        {
            r1[b].push_back(a-1);
        }
    }
    int maxr1[n],maxrn[n];
    for(int j = n-1;j >= 0;--j)
    {
        int rg = j-1;
        for(int u = 0;u < rn[j].size();++u)
        {
            rg = max(rg,rn[j][u]);
        }
        while(st1.size() && st1.back().first <= rg+1)
        {
            rg = max(rg,st1.back().second);
            st1.pop_back();
        }
        maxr1[j] = rg+1;
        if(rg >= j)
            st1.push_back({j,rg});
        rg = j-1;
        for(int u = 0;u < r1[j].size();++u)
        {
            rg = max(rg,r1[j][u]);
        }
        while(stn.size() && stn.back().first <= rg+1)
        {
            rg = max(rg,stn.back().second);
            stn.pop_back();
        }
        maxrn[j] = rg+1;
        if(rg >= j)
            stn.push_back({j,rg});
    }
    for(int j = n-1;j >= 0;--j)
    {
        for(int c = 0;c < alf;++c)
        {
            if(j == n-1)
            {
                dp[0][c][j] = 0;
                dp[1][c][j] = 0;
            }
            else
            {
                if(maxr1[j] != j)
                {
                    dp[1][c][j] = dp[1][c][maxr1[j]];
                }
                else
                {
                    dp[1][c][j] = add(dp[1][c][j+1],suf[c+1][j+1]);
                }
                if(maxrn[j] != j)
                {
                    dp[0][c][j] = dp[0][c][maxrn[j]];
                }
                else
                {
                    dp[0][c][j] = add(dp[0][c][j+1],pref[c][j+1]);
                }
            }
            pref[c+1][j] = add(pref[c][j],add(dp[0][c][j],dp[1][c][j]+1));
        }
        for(int c = alf-1;c >= 0;--c)
        {
            suf[c][j] = add(suf[c+1][j],add(dp[0][c][j],dp[1][c][j]+1));
        }
    }
    cout << pref[alf][0];
    return 0;
}

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