Submission #1271632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271632		tvgk	Misspelling (JOI22_misspelling)	C++20	100 / 100	299 ms	137364 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7, mxX = 'z' - 'a', MOD = 1e9 + 7;

int n, m, dp[mxN][28][2];
stack<int> stk[2];
vector<ii> query[mxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;

        if (u < v)
            query[u].push_back({v, 0});
        else
            query[v].push_back({u, 1});
    }

    for (int i = 0; i <= mxX; i++)
    {
        dp[n][i][0] = 1;
        stk[0].push(n);
        stk[1].push(n);
    }

    for (int i = n - 1; i >= 1; i--)
    {
        ll sum = 0;
        for (int j = mxX; j >= 0; j--)
        {
            dp[i][j][0] = (sum + dp[i + 1][j][0]) % MOD;
            sum = (sum + dp[i + 1][j][0] + dp[i + 1][j][1]) % MOD;
        }

        sum = 0;
        for (int j = 0; j <= mxX; j++)
        {
            dp[i][j][1] = (sum + dp[i + 1][j][1]) % MOD;
            sum = (sum + dp[i + 1][j][0] + dp[i + 1][j][1]) % MOD;
        }

        stk[0].push(i);
        stk[1].push(i);
        for (ii j : query[i])
        {
            while (stk[j.se].top() < j.fi)
                stk[j.se].pop();
        }

        for (int j = 0; j <= mxX; j++)
        {
            for (int tt = 0; tt <= 1; tt++)
                dp[i][j][tt] = dp[stk[tt].top()][j][tt];
        }
    }

    ll ans = 0;
    for (int i = 0; i <= mxX; i++)
        ans = (ans + dp[1][i][0] + dp[1][i][1]) % MOD;
    cout << ans;
}

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