結果

問題 No.318 学学学学学
ユーザー Jikky1618
提出日時 2025-02-11 20:53:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 4,397 bytes
コンパイル時間 4,233 ms
コンパイル使用メモリ 298,064 KB
実行使用メモリ 18,812 KB
最終ジャッジ日時 2025-02-11 20:53:49
合計ジャッジ時間 7,708 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <class S, class T>
struct Intervals {
    static constexpr S INF = numeric_limits<S>::max() / 2;
    static constexpr S L = -INF, R = INF;

    T none_val;
    int total_num;  // none_val でない区間の個数
    S total_len;    // none_val でない区間の長さの合計
    map<S, T> data;

    // コンストラクタ：全体 [L, R) を none_val に初期化
    Intervals(T nv = -1) : none_val(nv), total_num(0), total_len(0) {
        data.emplace(L, none_val);
        data.emplace(R, none_val);
    }

    // 区間 [l, r) の値を v に設定
    void set(S l, S r, T v) {
        assert(L <= l && r < R);
        if (l >= r) return;
        auto it_l = split(l), it_r = split(r);
        // [l, r) に含まれる既存の区間をすべて削除
        for (auto it = it_l; it != it_r;) {
            if (it->second != none_val) {
                S seg_l = it->first, seg_r = next(it)->first;
                total_len -= (seg_r - seg_l);
                total_num--;
            }
            it = data.erase(it);
        }
        // 新たに [l, r) を挿入
        auto it = data.emplace(l, v).first;
        if (v != none_val) {
            total_len += (r - l);
            total_num++;
        }
        // 左側との結合
        if (it != data.begin()) {
            auto it_prev = prev(it);
            if (it_prev->second == v) {
                data.erase(it);
                total_num--;
                l = it_prev->first;
                it = it_prev;
            }
        }
        // 右側との結合
        auto it_next = next(it);
        if (it_next != data.end() && it_next->second == v) {
            data.erase(it_next);
            total_num--;
        }
    }

    // 点 i が含まれる [i, i + 1) の値を返す
    T get_value(S i) {
        assert(L <= i && i < R);
        auto it = prev(data.upper_bound(i));
        return it->second;
    }

    // 点 i が含まれる区間 [l, r) とその値 v を返す
    tuple<S, S, T> get(S i) {
        assert(L <= i && i < R);
        auto it_r = data.upper_bound(i), it_l = prev(it_r);
        return make_tuple(it_l->first, it_r->first, it_l->second);
    }

    // 区間 [l, r) 内の区間を（境界ごとに分割した） run-length 圧縮結果として返す
    vector<tuple<S, S, T>> get(S l, S r) {
        assert(L <= l && r < R);
        vector<tuple<S, S, T>> res;
        if (l >= r) return res;
        auto it_r = data.upper_bound(l), it_l = prev(it_r);
        while (it_l->first < r) {
            res.emplace_back(max(l, it_l->first), min(it_r->first, r), it_l->second);
            it_l = it_r++;
        }
        return res;
    }

   private:
    // 点 pos において区間を分割し，すでに境界があればその位置のイテレータを返す
    // そうでなければ，その区間 [l, r) を [l, pos) と [pos, r) に分割し，後者の先頭を返す
    typename map<S, T>::iterator split(S pos) {
        auto it = data.lower_bound(pos);
        if (it != data.end() && it->first == pos) return it;
        T v = prev(it)->second;
        auto res = data.emplace(pos, v).first;
        if (v != none_val) total_num++;
        return res;
    }
};

template <class T>
vector<T> compress(vector<T>& v) {
    vector<T> res(v);
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    for (auto&& elem : v) elem = lower_bound(res.begin(), res.end(), elem) - res.begin();
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    auto comp = compress(A);
    int M = comp.size();
    vector<set<int>> P(M);
    for (int i = 0; i < N; i++) P[A[i]].emplace(i);

    Intervals<int, int> I;
    for (int i = 0; i < M; i++) {
        if (P[i].empty()) continue;
        int l = *P[i].begin(), r = *P[i].rbegin();
        // [l, r] を comp[i] に設定
        I.set(l, r + 1, comp[i]);
    }

    vector<int> B(N);
    for (auto [l, r, v] : I.get(0, N)) {
        for (int i = l; i < r; i++) B[i] = v;
    }

    for (int i = 0; i < N; i++) {
        cout << B[i] << " \n"[i == N - 1];
    }
}
0