結果

問題 No.2292 Interval Union Find
コンテスト
ユーザー Jikky1618
提出日時 2024-12-22 21:47:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 307 ms / 5,000 ms
コード長 3,502 bytes
コンパイル時間 3,526 ms
コンパイル使用メモリ 254,400 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-12-22 21:47:53
合計ジャッジ時間 16,122 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

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, Q;
    cin >> N >> Q;

    Intervals<int, int> I;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int L, R;
            cin >> L >> R;
            // [L, R) を 1 にする
            I.set(L, R, 1);
        }
        if (type == 2) {
            int L, R;
            cin >> L >> R;
            // [L, R) を -1 にする
            I.set(L, R, -1);
        }
        if (type == 3) {
            int u, v;
            cin >> u >> v;
            if (u > v) swap(u, v);
            // (u, v) がつながっているか
            auto [l, r, val] = I.get(u);
            // debug(u, v, l, r, val);
            cout << ((u == v) || (val != -1 && v <= r) ? 1 : 0) << '\n';
        }
        if (type == 4) {
            int v;
            cin >> v;
            // v が含まれる区間幅
            auto [l1, r1, val1] = I.get(v - 1);
            auto [l2, r2, val2] = I.get(v);
            // debug(v, l, r, val);
            if (val1 == val2) {
                cout << (val1 != -1 ? r2 - l1 + 1 : 1) << '\n';
            } else if (val1 == 1) {
                cout << r1 - l1 + 1 << '\n';
            } else {
                cout << r2 - l2 + 1 << '\n';
            }
        }
    }
}
0