Submission #690054

#	Time	Username	Problem	Language	Result	Execution time	Memory
690054		vjudge1	Misspelling (JOI22_misspelling)	C++17	100 / 100	1006 ms	240248 KiB

misspelling

#include <iostream>
#include <vector>
#include <set>

#define fi first
#define se second

using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int n, m;
pair <int, int> a[maxn];
int out[maxn], out1[maxn];
int pre[maxn][30], suf[maxn][30], cnt[30];
int f[maxn][30];
int sum;
bool d[maxn], d1[maxn];
set <int> s, s1;
vector <int> v[maxn], v1[maxn];

int main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> a[i].fi >> a[i].se;
        if(a[i].fi < a[i].se) {
            d[a[i].fi] = 1;
            out[a[i].fi] = max(out[a[i].fi], a[i].se);
        }
        else {
            d1[a[i].se] = 1;
            out1[a[i].se] = max(out1[a[i].se], a[i].fi);
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(i == 1) {
             for(int j = 1; j <= 26; ++j) f[i][j] = 1;
        }
        else {
            int x, y;
            if(s.empty()) x = 0;
            else x = *(--s.end());
            if(s1.empty()) y = 0;
            else y = *(--s1.end());
            for(int j = 1; j <= 26; ++j) {
                f[i][j] = (0ll + sum - pre[x][j - 1] - suf[y][j + 1] - cnt[j] + 3ll * mod) % mod;
            }
        }
        for(int j = 1; j <= 26; ++j) sum = (sum + f[i][j]) % mod;
        for(int j = 1; j <= 26; ++j) cnt[j] = (cnt[j] + f[i][j]) % mod;
        int sum1 = 0;
        for(int j = 1; j <= 26; ++j) {
            sum1 += f[i][j];
            sum1 %= mod;
            pre[i][j] = pre[i - 1][j] + sum1;
            pre[i][j] %= mod;
        }
        sum1 = 0;
        for(int j = 26; j >= 1; --j) {
            sum1 += f[i][j];
            sum1 %= mod;
            suf[i][j] = suf[i - 1][j] + sum1;
            suf[i][j] %= mod;
        }
        if(d[i]) {
            v[out[i]].push_back(i);
            s.insert(i);
        }
        if(d1[i]) {
            v1[out1[i]].push_back(i);
            s1.insert(i);
        }
        for(int j : v[i]) s.erase(j);
        for(int j : v1[i]) s1.erase(j);


    }
    cout << sum;
    return 0;
}

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