結果

問題 No.3017 交互浴
コンテスト
ユーザー みねしみねみね
提出日時 2025-07-02 23:50:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 5,187 bytes
コンパイル時間 3,786 ms
コンパイル使用メモリ 284,972 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2025-07-02 23:51:11
合計ジャッジ時間 26,745 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意
#endif
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath> // M_PIを使用するため
using namespace std;

using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (ll)n - 1; i >= 0; --i)

const ll null = -1LL;
template <typename T>
using vc = vector<T>; // prioriy_queueに必要なのでここにこれ書いてます
template <typename T>
using vv = vc<vc<T>>;
template <typename T>
using vvv = vv<vc<T>>;
using vl = vc<ll>;
using vvl = vv<ll>;
using vvvl = vv<vl>;
using vvvvl = vv<vvl>;
using vs = vc<string>;
using vvs = vv<string>;
using vb = vc<bool>;
using vvb = vc<vb>;
using P = pair<ll, ll>;

template <class T>
istream &operator>>(istream &i, vc<T> &v)
{
    rep(j, size(v)) i >> v[j];
    return i;
}
// それぞれ「下，上，右，左」に対応
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

#define nall(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define next_p(v) next_permutation(v.begin(), v.end())

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;   // 区間の色を表す
    ll 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.em(L, none_val);
        data.em(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);
        }

        // 新たに区間を挿入
        auto it = data.em(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;
    }
};

void solve()
{
    ll n;
    cin >> n;
    vl h(n);
    cin >> h;

    Intervals<ll, ll> I(0);
    rep(i, n)
    {
        I.set(0, h[i], ((i & 1) ^ 1ll));
        cout << I.total_len << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll testcases = 1ll;
    // cin >> testcases;
    rep(_, testcases) solve();

    return 0;
}
0