#1037854 (C++23) No.3017 交互浴

提出ソース
結果

問題	No.3017 交互浴
ユーザー	Tatsu_mr
提出日時	2025-01-25 13:35:26
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	202 ms / 2,000 ms
コード長	7,292 bytes
コンパイル時間	6,653 ms
コンパイル使用メモリ	281,012 KB
実行使用メモリ	9,728 KB
最終ジャッジ日時	2025-01-25 22:51:29
合計ジャッジ時間	14,704 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 55
権限があれば一括ダウンロードができます
ソースコード

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

template <class S, class T, T e = 0>
struct IntervalSet {
    public:
    struct Node {
        S l, r;
        T val;
        
        bool operator<(const Node &a) const {
            return (l != a.l ? l < a.l : r < a.r);
        }
    };
    
    IntervalSet() {
        s.insert({-SINF, -SINF, e});
        s.insert({SINF, SINF, e});
    }
    
    bool covered(S l, S r) {
        assert(l <= r);
        if (l == r) {
            return true;
        }
        auto it = prev(s.upper_bound({l, SINF, e}));
        return (it->l <= l && r <= it->r);
    }
    
    bool covered(S x) {
        return covered(x, x + 1);
    }
    
    // [l, r) を含む区間 なければ [l, r) のすぐ左の区間
    auto get(S l, S r) {
        assert(l < r);
        return prev(s.upper_bound({l, SINF, e}));
    }
    
    auto get(S x) {
        return get(x, x + 1);
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, T x, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, e}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            if (x == X) {
                goto adjust;
            }
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            add(l, r, x);
            s.insert({l, r, x});
            goto adjust;
        }
        if (it->l <= l && l <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (x == X) {
                l = L;
            } else {
                if (L < l) {
                    add(L, l, X);
                    s.insert({L, l, X});
                }
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l <= r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (x == X) {
                r = R;
            } else {
                if (r < R) {
                    add(r, R, X);
                    s.insert({r, R, X});
                }
            }
        }
        add(l, r, x);
        s.insert({l, r, x});
        
        adjust:
        it = s.lower_bound({l, r, x});
        auto pit = prev(it);
        auto nit = next(it);
        if (pit->r == it->l && pit->val == it->val) {
            if (it->r == nit->l && it->val == nit->val) {
                S L = pit->l, R = nit->r;
                T X = it->val;
                del(pit->l, pit->r, pit->val);
                s.erase(pit);
                del(it->l, it->r, it->val);
                s.erase(it);
                del(nit->l, nit->r, nit->val);
                s.erase(nit);
                add(L, R, X);
                s.insert({L, R, X});
            } else {
                S L = pit->l, R = it->r;
                T X = it->val;
                del(pit->l, pit->r, pit->val);
                s.erase(pit);
                del(it->l, it->r, it->val);
                s.erase(it);
                add(L, R, X);
                s.insert({L, R, X});
            }
        } else if (it->r == nit->l && it->val == nit->val) {
            S L = it->l, R = nit->r;
            T X = it->val;
            del(it->l, it->r, it->val);
            s.erase(it);
            del(nit->l, nit->r, nit->val);
            s.erase(nit);
            add(L, R, X);
            s.insert({L, R, X});
        }
        return;
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, ADD add, DEL del) {
        insert(l, r, T(0), add, del);
    }
    
    void insert(S l, S r, T x = 0) {
        auto func = [](S l, S r, T x) {};
        insert(l, r, x, func, func);
    }
    
    void insert(S l) {
        auto func = [](S l, S r, T x) {};
        insert(l, l + 1, T(0), func, func);
    }
    
    template <class ADD, class DEL>
    void erase(S l, S r, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, e}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            return;
        }
        if (it->l <= l && l < it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l < r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            add(r, R, X);
            s.insert({r, R, X});
        }
        return;
    }
    
    void erase(S l, S r) {
        auto func = [](S l, S r, T x) {};
        erase(l, r, func, func);
    }
    
    void erase(S l) {
        auto func = [](S l, S r, T x) {};
        erase(l, l + 1, func, func);
    }
    
    int size() {
        return (int)s.size() - 2;
    }
    
    S mex(S x = 0) {
        auto it = prev(s.upper_bound({x, SINF, e}));
        if (it->l <= x && x < it->r) {
            return it->r;
        } else {
            return x;
        }
    }
    
    void dump() {
        for (auto node : s) {
            if (abs(node.l) != SINF) {
                cout << "[" << node.l << ", " << node.r << "):";
                cout << node.val;
                cout << " ";
            }
        }
        cout << endl;
    }
    
    private:
    set<Node> s;
    S SINF = numeric_limits<S>::max();
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    IntervalSet<int, int> s;
    int ans = 0;
    auto add = [&](int l, int r, int x) {
        if (x == 1) {
            ans += r - l;
        }
    };
    auto del = [&](int l, int r, int x) {
        if (x == 1) {
            ans -= r - l;
        }
    };
    s.insert(0, INF, 0, add, del);
    int n;
    cin >> n;
    rep(i, n) {
        int h;
        cin >> h;
        if (i % 2 == 0) {
            s.insert(0, h, 1, add, del);
        } else {
            s.insert(0, h, 0, add, del);
        }
        cout << ans << "\n";
    }
}
yukicoder

結果

ソースコード
