Submission #904264

#	Time	Username	Problem	Language	Result	Execution time	Memory
904264		Tuanlinh123	Misspelling (JOI22_misspelling)	C++17	100 / 100	906 ms	149868 KiB

misspelling

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const long long maxn=500005, Mod=1e9+7;
vector <pll> e[maxn];
long long dp[maxn][26];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m; cin >> n >> m;
    for (ll i=1; i<=m; i++)
    {
        ll l, r; cin >> l >> r;
        if (l>r)
        {
            swap(l, r);
            e[l+1].pb({0, l});
            e[r+1].pb({0, -l});
        }
        else
        {
            e[l+1].pb({1, l});
            e[r+1].pb({1, -l});
        }
    }
    multiset <ll> S[2];
    for (ll i=0; i<26; i++) dp[1][i]=i+1;
    for (pll i:e[1]) S[i.fi].insert(i.se);
    for (ll i=2; i<=n; i++)
    {
        for (pll i:e[i])
        {
            if (i.se<0) S[i.fi].erase(S[i.fi].find(-i.se));
            else S[i.fi].insert(i.se);
        }
        ll p0=(S[0].size() ? *prev(S[0].end()) : 0), p1=(S[1].size() ? *prev(S[1].end()) : 0);
        for (ll d=0; d<26; d++)
        {
            if (d) dp[i][d]=(dp[i][d]+dp[i-1][d-1]-dp[p0][d-1]+Mod)%Mod;
            dp[i][d]=(dp[i][d]+(dp[i-1][25]-dp[p1][25]-dp[i-1][d]+dp[p1][d])+Mod*2)%Mod;
            if (d) dp[i][d]=(dp[i][d]+dp[i][d-1])%Mod;
        }
        for (ll d=0; d<26; d++) dp[i][d]=(dp[i][d]+dp[i-1][d])%Mod;
    }
    cout << dp[n][25];
}

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