Submission #53502825

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/modint>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int N, H;
    cin >> N >> H;

    vector<int> X(N);
    for (int& x : X) {
        cin >> x;
    }

    vector<int> indices(N);
    iota(begin(indices), end(indices), 0);
    ranges::sort(indices, {}, [&](const int i) { return X[i]; });

    vector<pair<int, int>> C(N);
    vector<vector<int>> comps;
    for (comps.push_back({}); const int i : indices) {
        if (!comps.back().empty() && X[i] - X[comps.back().back()] > H) {
            comps.push_back({});
        }
        comps.back().push_back(i);
        C[i] = {int(comps.size()) - 1, int(comps.back().size() - 1)};
    }

    vector<int> prev_smaller(N), left_count(N);
    for (stack<int> s; const int i : indices) {
        if (!s.empty() && X[i] - X[s.top()] > H) {
            s = stack<int>();
        }
        while (!s.empty() && s.top() > i) {
            s.pop();
        }
        if (s.empty()) {
            prev_smaller[i] = -1;
            left_count[i] = 0;
        } else {
            prev_smaller[i] = s.top();
            left_count[i] = left_count[prev_smaller[i]] + 1;
        }
        s.push(i);
    }

    vector<int> next_smaller(N), right_count(N);
    for (stack<int> s; const int i : views::reverse(indices)) {
        if (!s.empty() && X[s.top()] - X[i] > H) {
            s = stack<int>();
        }
        while (!s.empty() && s.top() > i) {
            s.pop();
        }
        if (s.empty()) {
            next_smaller[i] = -1;
            right_count[i] = 0;
        } else {
            next_smaller[i] = s.top();
            right_count[i] = right_count[next_smaller[i]] + 1;
        }
        s.push(i);
    }

    vector<int> forced_moves(N);
    for (const auto& comp : comps) {
        for (int i = 0; i < int(comp.size()); i++) {
            if (i - 1 >= 0) {
                forced_moves[comp[i]] += comp[i - 1] > comp[i];
            }
            if (i + 1 < int(comp.size())) {
                forced_moves[comp[i]] += comp[i + 1] > comp[i];
            }
        }
    }

    vector<mint> pow2(N + 1);
    pow2[0] = 1;
    for (int i = 1; i <= N; i++) {
        pow2[i] = 2 * pow2[i - 1];
    }

    vector<mint> p(N);
    for (int i = 0; i < N; i++) {
        p[i] = 1;
        // cout << i << ": " << left_count[i] << " " << right_count[i] << " "
        //      << forced_moves[i] << "\n";
        p[i] /= pow2[left_count[i] + right_count[i]];
        p[i] *= mint(2 - forced_moves[i]) / 2;
    }

    auto op = [](mint x, mint y) { return x * y; };
    auto e = []() { return 1; };
    segtree<mint, op, e> seg(vector<mint>(comps.size(), 0));
    for (int i = 0; i < N; i++) {
        auto [comp, _] = C[i];
        const mint prev = seg.get(comp);
        seg.set(comp, p[i]);
        cout << (seg.all_prod() * pow2[N]).val() << " ";
        seg.set(comp, prev + p[i]);
    }
    cout << "\n";

    return 0;
}

Submission Info

Judge Result