Submission #835987

#	Time	Username	Problem	Language	Result	Execution time	Memory
835987		PurpleCrayon	Misspelling (JOI22_misspelling)	C++17	100 / 100	212 ms	156068 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e5+10, MOD = 1e9+7;
const int K = 26;

void add_self(int& a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void sub_self(int& a, int b) {
    a -= b;
    if (a < 0) a += MOD;
}

void add_self(ar<int, K>& a, ar<int, K>& b) {
    for (int i = 0; i < K; i++) add_self(a[i], b[i]);
}

void sub_self(ar<int, K>& a, ar<int, K>& b) {
    for (int i = 0; i < K; i++) sub_self(a[i], b[i]);
}

int n, m;
int last_one[N], last_two[N];
ar<int, K> dp[N];

struct Stack {
    vector<pair<int, ar<int, K>>> st;
    ar<int, K> net;

    Stack() {
        st.emplace_back(N, ar<int, K>{});
        net.fill(0);
    }

    void pop_less(int k) {
        while (st.back().first < k) {
            sub_self(net, st.back().second);
            st.pop_back();
        }
    }

    ar<int, K> sum() {
        return net;
    }

    void push_final(int r, ar<int, K>& cur) {
        st.emplace_back(r, cur);
        add_self(net, cur);
    }
};

void solve() {
    cin >> n >> m;
    memset(last_one, -1, sizeof(last_one));
    memset(last_two, -1, sizeof(last_two));
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b, --a, --b;
        if (a < b) {
            last_one[a] = max(last_one[a], b);
        } else {
            last_two[b] = max(last_two[b], a);
        }
    }

    dp[n-1].fill(1); // ending state

    Stack st_one, st_two;
    for (int i = n-2; i >= 0; i--) {
        st_one.pop_less(last_one[i]);
        st_two.pop_less(last_two[i]);

        if (last_one[i] <= i) {
            st_one.push_final(i, dp[i+1]);
        }

        if (last_two[i] <= i) {
            st_two.push_final(i, dp[i+1]);
        }

        dp[i].fill(1);
        ar<int, K> one = st_one.sum();
        ar<int, K> two = st_two.sum();
        for (int j = 1; j < K; j++) add_self(one[j], one[j-1]);
        for (int j = K-2; j >= 0; j--) add_self(two[j], two[j+1]);
        for (int j = 0; j < K; j++) {
            if (j) add_self(dp[i][j], one[j-1]);
            if (j < K-1) add_self(dp[i][j], two[j+1]);
        }
    }

    int ans = 0;
    for (int i = 0; i < K; i++) add_self(ans, dp[0][i]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    solve();
}

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