Submission #1178325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178325		ace5	Misspelling (JOI22_misspelling)	C++20	100 / 100	1049 ms	217612 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int st1[maxlog][maxn],stn[maxlog][maxn];
int maxst[maxn];
int dp[2][alf][maxn];

int MAX1(int l,int r)
{
    if(l > r)
        return 0;
    return max(st1[maxst[r-l+1]][l],st1[maxst[r-l+1]][r-(1<<maxst[r-l+1])+1]);
}
int MAXn(int l,int r)
{
    if(l > r)
        return 0;
    return max(stn[maxst[r-l+1]][l],stn[maxst[r-l+1]][r-(1<<maxst[r-l+1])+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tst = 0;
    for(int i = 1;i < maxn;++i)
    {
        maxst[i] = tst;
        if((1<<(tst+1)) <= i+1)
        {
            tst++;
        }
    }
    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)
    {
        maxr1[j] = j;
        for(int u = 0;u < rn[j].size();++u)
        {
            maxr1[j] = max(maxr1[j],rn[j][u]+1);
            maxr1[j] = max(maxr1[j],MAX1(j+1,rn[j][u]));
        }
        for(int y = 0;j+(1<<y) <= n;++y)
        {
            st1[y][j] = (y == 0 ? maxr1[j] : max(st1[y-1][j],st1[y-1][j+(1<<(y-1))]));
        }
        maxrn[j] = j;
        for(int u = 0;u < r1[j].size();++u)
        {
            maxrn[j] = max(maxrn[j],r1[j][u]+1);
            maxrn[j] = max(maxrn[j],MAXn(j+1,r1[j][u]));
        }
        for(int y = 0;j+(1<<y) <= n;++y)
        {
            stn[y][j] = (y == 0 ? maxrn[j] : max(stn[y-1][j],stn[y-1][j+(1<<(y-1))]));
        }
       // cout << maxr1[j] << ' ' << maxrn[j] << endl;
    }
    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] = dp[1][c][j+1];
                    for(int h = c+1;h < alf;++h)
                    {
                        dp[1][c][j] = (dp[1][c][j] + ll(dp[0][h][j+1] + dp[1][h][j+1]) + 1)%mod;
                    }
                }
                if(maxrn[j] != j)
                {
                    dp[0][c][j] = dp[0][c][maxrn[j]];
                }
                else
                {
                    dp[0][c][j] = dp[0][c][j+1];
                    for(int h = 0;h < c;++h)
                    {
                        dp[0][c][j] = (dp[0][c][j] + ll(dp[0][h][j+1] + dp[1][h][j+1]) + 1)%mod;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i < alf;++i)
    {
        ans = (ans + ll(dp[0][i][0] + dp[1][i][0]) + 1)%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