Submission #996674

#	Time	Username	Problem	Language	Result	Execution time	Memory
996674		onbert	Misspelling (JOI22_misspelling)	C++17	100 / 100	3716 ms	367184 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, M = 1e9 + 7;
int n, m;
int a[maxn][26];
int fen[maxn][26][2];
void update(int id, int j, int t, int val) {
    if (t==2) {
        a[id][j] += val;
        update(id, j, 0, val); update(id, j, 1, val);
        return;
    }
    while (id<=n+1) {
        fen[id][j][t] = fen[id][j][t] + val + M;
        while (fen[id][j][t]>=M) fen[id][j][t] -= M;
        id += (id & -id);
    }
}
int qry(int id, int j, int t) {
    int sum = 0;
    while (id>=1) {
        sum = sum + fen[id][j][t];
        while (sum>=M) sum -= M;
        id -= (id & -id);
    }
    return sum;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int R[n+1][2];
    for (int i=1;i<=n;i++) R[i][0] = -1, R[i][1] = -1;
    for (int i=1;i<=m;i++) {
        int x, y;
        cin >> x >> y;
        if (x<y) R[x][0] = max(y, R[x][0]);
        if (x>y) R[y][1] = max(x, R[y][1]);
    }
    set<int> exist[2];
    for (int i=1;i<=n+1;i++) exist[0].insert(i), exist[1].insert(i);
    for (int i=0;i<26;i++) update(n, i, 2, 1);
    for (int l=n-1;l>=1;l--) {
        for (int t=0;t<=1;t++) {
            int r = R[l][t];
            if (r==-1) continue;
            while (true) {
                int cur = *exist[!t].lower_bound(l+1);
                if (cur > r) break;
                for (int j=0;j<26;j++) update(cur, j, !t, -a[cur][j]);
                exist[!t].erase(cur);
                // cout << "del " << cur << " " << !t << endl;
            }
        }
        int cur = 1;
        for (int j=0;j<26;j++) cur = (cur + qry(n, j, 1) - qry(l, j, 1)) % M;
        for (int j=0;j<26;j++) {
            cur = (cur - (qry(n, j, 1) - qry(l, j, 1)) + M) % M;
            update(l, j, 2, cur);
            cur = (cur + (qry(n, j, 0) - qry(l, j, 0)) + M) % M;
        }
    }
    int ans = 0;
    for (int i=0;i<26;i++) ans = (ans + a[1][i]) % M;
    cout << ans << endl;
}

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