結果

問題 No.3017 交互浴
コンテスト
ユーザー hamikan
提出日時 2025-12-07 17:27:50
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 461 ms / 2,000 ms
コード長 2,341 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,998 ms
コンパイル使用メモリ 202,424 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-07 17:28:20
合計ジャッジ時間 27,540 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

template<typename T>
struct RangeSet {
    map<T, T> mp;
    T total;
    
    RangeSet() : total(0) {}

    bool empty() const {
        return mp.empty();
    }

    bool contains(T x) const {
        auto it = mp.upper_bound(x);
        if(it == mp.begin()) return false;
        return prev(it)->first <= x && x < prev(it)->second;
    }

    bool intersects(T l, T r) const {
        if(l >= r) return false;
        auto it = mp.lower_bound(l);
        if(it != mp.end() && it->first < r) return true;
        if(it == mp.begin()) return false;
        return prev(it)->second > l;
    }

    bool covered(T l, T r) const {
        if(l >= r) return true;
        auto it = mp.upper_bound(l);
        if(it == mp.begin()) return false;
        return prev(it)->first <= l && r <= prev(it)->second;
    }
    
    void insert(T l, T r) {
        if(l >= r) return;
        auto it = mp.lower_bound(l);
        if(it != mp.begin() && l <= prev(it)->second) it = prev(it);
        while(it != mp.end() && it->first <= r) {
            l = min(l, it->first);
            r = max(r, it->second);
            total -= (it->second - it->first);
            it = mp.erase(it);
        }
        mp[l] = r;
        total += (r - l);
    }

    void erase(T l, T r) {
        if(l >= r) return;
        auto it = mp.lower_bound(l);
        if(it != mp.begin() && l < prev(it)->second) it = prev(it);
        while(it != mp.end() && it->first < r) {
            auto [L, R] = *it;
            it = mp.erase(it);
            total -= (R - L);
            if(L < l) {
                mp[L] = l;
                total += (l - L);
            }
            if(r < R) {
                mp[r] = R;
                total += (R - r);
                break;
            }
        }
    }

    T mex(T x) const {
        auto it = mp.upper_bound(x);
        if(it == mp.begin()) return x;
        return max(x, prev(it)->second);
    }

    T sum() const { return total; }
    auto begin() const { return mp.begin(); }
    auto end() const { return mp.end(); }
};

int main() {
    int N;
    cin >> N;
    RangeSet<ll> ans;
    for(int i=0; i<N; i++) {
        int H; cin >> H;
        if(i % 2) ans.erase(0, H);
        else ans.insert(0, H);
        cout << ans.sum() << endl;
    }
}
0