結果

問題 No.3017 交互浴
ユーザー Jikky1618
提出日時 2025-01-25 14:29:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,727 bytes
コンパイル時間 4,955 ms
コンパイル使用メモリ 286,452 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-01-25 23:22:27
合計ジャッジ時間 29,264 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 50 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

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;
    // data[l] : 区間 [l, r) に割り当てられた値（r は次の区間の l）
    map<S, T> data;

    // 定義域を [L, R) とし，[L, R) = none_val で初期化
    Intervals(T none_val = -1) {
        data[L] = none_val;
        data[R] = none_val;
    }

    // [l, r) = v
    void set(S l, S r, T v = 1) {
        l = max(l, L), r = min(r, R);
        if (l >= r) return;
        auto it = data.upper_bound(l);
        auto pit = prev(it);
        T vR = pit->second;
        if (pit->first == l) {
            pit = data.erase(pit);
            pit = prev(pit);
        }
        T vL = pit->second;
        // 丸ごと上書きされる区間は削除
        while (it != data.end()) {
            if (it->first > r) break;
            vR = it->second;
            it = data.erase(it);
        }
        if (v != vR) data[r] = vR;
        if (v != vL) data[l] = v;
    }

    // a[i]
    T get_value(S i) {
        assert(L <= i && i < R);
        return prev(data.upper_bound(i))->second;
    }

    // i を含む値の等しい極大区間が [l, r) = v としたとき {l, r, v} を返す
    tuple<S, S, T> get(S i) {
        assert(L <= i && i < R);
        auto it = data.upper_bound(i);
        auto pit = prev(it);
        return {pit->first, it->first, pit->second};
    }

    // [l, r) を連長圧縮した結果を {左端, 右端, 値} のリストとして返す
    vector<tuple<S, S, T>> get_all(S l, S r) {
        l = max(l, L), r = min(r, R);
        if (l >= r) return vector<tuple<S, S, T>>();
        vector<tuple<S, S, T>> res;
        auto nit = data.upper_bound(l), it = prev(nit);
        T i = it->first;
        while (i < r) {
            T ni = nit->first;
            res.emplace_back(max(i, l), min(ni, r), it->second);
            i = ni;
            it = nit++;
        }
        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;
    I.set(0, 1e9 + 1, 0);  // 緑
    for (int i = 0; i < N; i++) {
        if (i & 1) {
            I.set(0, H[i], 0);  // 緑
        } else {
            I.set(0, H[i], 1);  // 水色
        }
        int ans = 0;
        for (auto [l, r, v] : I.get_all(0, 1e9 + 1)) {
            if (v == 1) ans += r - l;
        }
        cout << ans << "\n";
    }
}
0