結果

問題 No.3017 交互浴
ユーザー じきお。
提出日時 2025-02-17 15:51:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 4,045 bytes
コンパイル時間 3,959 ms
コンパイル使用メモリ 287,940 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2025-02-17 15:51:28
合計ジャッジ時間 19,794 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 <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) {
        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;
    }
};
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];
    ll ans = 0;
    Intervals<int, int> I(0);
    for (int i = 0; i < N; i++) {
        // i 回目の入浴で上書きされる水色の区間
        ll sub = 0;
        for (auto [l, r, c] : I.get(0, H[i])) {
            if (c == 1) sub += (r - l);
        }
        ans -= sub;
        if (i & 1) {
            I.set(0, H[i], 0);  // 緑
        } else {
            I.set(0, H[i], 1);  // 水色
            ans += H[i];
        }
        cout << ans << "\n";
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0