제출 #952424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952424		EJIC_B_KEDAX	Misspelling (JOI22_misspelling)	C++17	100 / 100	783 ms	72360 KiB

misspelling

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(time(0));

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << fixed << setprecision(30);
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

const int LG = 19, N = 1 << LG, A = 26, mod = 1000000007;
int to_up[N], to_down[N], dp[N][A];

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a - b + mod;
}

int mul(int a, int b) {
    return 1ll * a * b % mod;
}

int bin_pow(int a, int x) {
    int res = 1;
    while (x) {
        if (x & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        x >>= 1;
    }
    return res;
}

struct segment_tree {
    vector<int> st;
    int size;
    segment_tree(int sz = N) {
        size = sz;
        st.resize(2 * size, -1);
    }
    void update(int l, int r, int v) {
        l += size;
        r += size;
        while (l <= r) {
            if (l & 1) {
                st[l] = max(st[l], v);
                l++;
            }
            if (~r & 1) {
                st[r] = max(st[r], v);
                r--;
            }
            l >>= 1;
            r >>= 1;
        }
    }
    int get(int i) {
        i += size;
        int res = -1;
        while (i) {
            res = max(st[i], res);
            i >>= 1;
        }
        return res;
    }
};

void init() {}

void solve() {
    int n, m;
    cin >> n >> m;
    segment_tree stl, str;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        if (a < b) {
            str.update(a + 1, b, a);
        } else {
            stl.update(b + 1, a, b);
        }
    }
    for (int i = 0; i < n; i++) {
        to_up[i] = stl.get(i);
        to_down[i] = str.get(i);
    }
    for (int i = 0; i < A; i++) {
        dp[0][i] = 1;
    }
    // for (int i = 0; i < n; i++) {
    //     cout << to_up[i] << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    //     cout << to_down[i] << ' ';
    // }
    // cout << '\n';
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < A; j++) {
            int up = 0, down = 0, plate = 0, anywhere = 0;
            if (to_up[i] != -1) {
                up = dp[to_up[i]][j];
            }
            if (to_down[i] != -1) {
                down = dp[to_down[i]][j];
            }
            if (to_up[i] > to_down[i]) {
                plate = down;
            } else {
                plate = up;
            }
            anywhere = sub(dp[i - 1][j], sub(add(up, down), plate));
            // cout << i << ' ' << j << ' ' << plate << ' ' << up << ' ' << down << ' ' << anywhere << '\n';
            up = sub(up, plate);
            down = sub(down, plate);
            for (int l = 0; l < A; l++) {
                dp[i][l] = add(dp[i][l], anywhere);
                if (l <= j) {
                    dp[i][l] = add(dp[i][l], down);
                }
                if (l >= j) {
                    dp[i][l] = add(dp[i][l], up);
                }
                if (l == j) {
                    dp[i][l] = add(dp[i][l], plate);
                }
            }
        }
    }
    int ans = 0;
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < A; j++) {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    for (int i = 0; i < A; i++) {
        ans = add(ans, dp[n - 1][i]);
    }
    cout << ans << '\n';
    // cout << sub(bin_pow(A, n), ans) << '\n';
}

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