結果

問題 No.3017 交互浴
コンテスト
ユーザー Jikky1618
提出日時 2025-02-09 02:49:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 4,879 bytes
コンパイル時間 3,810 ms
コンパイル使用メモリ 282,692 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2025-02-09 02:50:19
合計ジャッジ時間 18,803 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

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

template <typename S, typename T>
struct Intervals {
    // 定数（使える座標の範囲を -INF～INF とする）
    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;  // key: 区間の左端。ある key から次の key までがその区間。

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

    // --- ヘルパー関数 split ---
    // 点 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;
        it--;
        T v = it->second;
        // [l, r) を [l,pos) と [pos,r) に分割．
        auto res = data.emplace(pos, v).first;
        // none_val でない区間なら，新たに1区間増えたので total_num を更新
        if (v != none_val) total_num++;
        return res;
    }

    // --- set 関数 ---
    // 区間 [l, r) の値を v に設定（必要なところで分割・結合する）
    void set(S l, S r, T v) {
        l = max(l, L), r = min(r, R);
        if (l >= r) return;
        // [l,r) の左右端に境界を作っておく
        auto itr_l = split(l), itr_r = split(r);
        // [l,r) に含まれる既存の区間をすべて削除し，その分の total_num, total_len を調整
        for (auto it = itr_l; it != itr_r;) {
            if (it->second != none_val) {
                S seg_l = it->first;
                auto it2 = next(it);
                S seg_r = (it2 == data.end() ? R : it2->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) {
                // 左側の区間 [L, l) と [l, r) を結合し，境界 l を削除
                data.erase(it);
                total_num--;         // ２区間がひとつになったので
                l = it_prev->first;  // 結合後の区間は [it_prev->first, r)
                it = it_prev;
            }
        }
        // 右側との結合
        auto it_next = next(it);
        if (it_next != data.end() && it_next->second == v) {
            data.erase(it_next);
            total_num--;
        }
    }

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

    // --- get (一点版) ---
    // 点 i が含まれる区間 [l, r) とその値 v を返す
    tuple<S, S, T> get(S i) {
        auto it = prev(data.upper_bound(i));
        S l = it->first;
        auto it2 = next(it);
        S r = (it2 == data.end() ? R : it2->first);
        return make_tuple(l, r, it->second);
    }

    // --- get (区間版) ---
    // 区間 [l,r) 内の区間を（境界ごとに分割した） run-length 圧縮結果として返す
    vector<tuple<S, S, T>> get(S l, S r) {
        l = max(l, L), r = min(r, R);
        vector<tuple<S, S, T>> res;
        if (l >= r) return res;
        auto it = split(l), itr_r = split(r);
        while (it != itr_r) {
            S seg_l = it->first;
            auto it2 = next(it);
            S seg_r = (it2 == data.end() ? R : it2->first);
            res.emplace_back(seg_l, seg_r, it->second);
            ++it;
        }
        return res;
    }
};

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