結果

問題 No.3017 交互浴
コンテスト
ユーザー Jikky1618
提出日時 2025-01-25 14:39:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 2,000 ms
コード長 3,564 bytes
コンパイル時間 3,380 ms
コンパイル使用メモリ 284,132 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2025-01-25 23:25:50
合計ジャッジ時間 13,626 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

// https://codeforces.com/contest/1638/problem/E
// 持つ値のタイプ T、座標タイプ X
// コンストラクタでは T none_val を指定する
template <typename T, typename X = ll>
struct Intervals {
    static constexpr X LLIM = numeric_limits<X>::lowest();
    static constexpr X RLIM = numeric_limits<X>::max();
    T none_val;
    // const T none_val;
    // none_val でない区間の個数と長さ合計
    int total_num;
    X total_len;
    map<X, T> dat;

    Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) {
        dat[LLIM] = none_val;
        dat[RLIM] = none_val;
    }

    // x を含む区間の情報の取得 l, r, t
    tuple<X, X, T> get(X x, bool ERASE = false) {
        auto it2 = dat.upper_bound(x);
        auto it1 = prev(it2);
        auto [l, tl] = *it1;
        auto [r, tr] = *it2;
        if (tl != none_val && ERASE) {
            --total_num, total_len -= r - l;
            dat[l] = none_val;
            merge_at(l);
            merge_at(r);
        }
        return {l, r, tl};
    }

    // [L, R) 内の全データの取得 f(l, r, t)
    template <typename F>
    void enumerate_range(X L, X R, F f, bool ERASE = false) {
        assert(LLIM <= L && L <= R && R <= RLIM);
        if (!ERASE) {
            auto it = prev(dat.upper_bound(L));
            while ((*it).first < R) {
                auto it2 = next(it);
                f(max((*it).first, L), min((*it2).first, R), (*it).second);
                it = it2;
            }
            return;
        }
        // 半端なところの分割
        auto p = prev(dat.upper_bound(L));
        if ((*p).first < L) {
            dat[L] = (*p).second;
            if (dat[L] != none_val) ++total_num;
        }
        p = dat.lower_bound(R);
        if (R < (*p).first) {
            T t = (*prev(p)).second;
            dat[R] = t;
            if (t != none_val) ++total_num;
        }
        p = dat.lower_bound(L);
        while (1) {
            if ((*p).first >= R) break;
            auto q = next(p);
            T t = (*p).second;
            f((*p).first, (*q).first, t);
            if (t != none_val) --total_num, total_len -= (*q).first - (*p).first;
            p = dat.erase(p);
        }
        dat[L] = none_val;
    }

    void set(X L, X R, T t) {
        assert(L <= R);
        if (L == R) return;
        enumerate_range(L, R, [](int l, int r, T x) -> void {}, true);
        dat[L] = t;
        if (t != none_val) total_num++, total_len += R - L;
        merge_at(L);
        merge_at(R);
    }

    template <typename F>
    void enumerate_all(F f) {
        enumerate_range(LLIM, RLIM, f, false);
    }

    void merge_at(X p) {
        if (p == LLIM || RLIM == p) return;
        auto itp = dat.lower_bound(p);
        assert((*itp).first == p);
        auto itq = prev(itp);
        if ((*itp).second == (*itq).second) {
            if ((*itp).second != none_val) --total_num;
            dat.erase(itp);
        }
    }
};

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

    Intervals<int, int> I(0);
    for (int i = 0; i < N; i++) {
        if (i & 1) {
            I.set(0, H[i], 0);  // 緑
        } else {
            I.set(0, H[i], 1);  // 水色
        }
        cout << I.total_len << "\n";
    }
}
0