結果

問題 No.2292 Interval Union Find
コンテスト
ユーザー C
提出日時 2026-10-02 02:00:18
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 289 ms / 5,000 ms
+ 330µs
コード長 2,312 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,602 ms
コンパイル使用メモリ 412,376 KB
実行使用メモリ 39,456 KB
最終ジャッジ日時 2026-10-02 02:00:53
合計ジャッジ時間 33,474 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using pll=pair<ll,ll>;

// using mint=modint;

// template<class K,class V>
// using ordered_map=tree<K,V,less<K>,rb_tree_tag,tree_order_statistics_node_update>;

struct Query{
    ll type,x,y;
};

struct S{
    ll mn,len;
};

S op(S a,S b){
    return {min(a.mn,b.mn),a.len+b.len};
}

S e(){
    return {1,0};
}

using F=ll;

F id(){
    return -1;
}

S mapping(F f,S x){
    if(f==-1||x.len==0)return x;
    return {f,x.len};
}

F composition(F f,F g){
    if(f==-1)return g;
    return f;
}

bool all_one(S x){
    return x.mn==1;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    ll N,Q;
    cin>>N>>Q;
    vector<Query>queries;
    vll xs;
    rep(i,0,Q){
        ll type;
        cin>>type;
        if(type<=3){
            ll x,y;
            cin>>x>>y;
            queries.push_back({type,x,y});
            xs.push_back(x),xs.push_back(y);
        }else{
            ll v;
            cin>>v;
            queries.push_back({type,v,0});
            xs.push_back(v);
        }
    }
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());

    auto get_id=[&](ll x){
        return lower_bound(xs.begin(),xs.end(),x)-xs.begin();
    };

    vector<S>init(xs.size()-1,{0,1});
    lazy_segtree<S,op,e,F,mapping,composition,id>seg(init);

    for(auto [type,x,y]:queries){
        if(type==1){
            ll l=get_id(x),r=get_id(y);
            seg.apply(l,r,1);
        }else if(type==2){
            ll l=get_id(x),r=get_id(y);
            seg.apply(l,r,0);
        }else if(type==3){
            if(x>y)swap(x,y);
            if(x==y){
                cout<<1<<endl;
                continue;
            }
            ll l=get_id(x),r=get_id(y);
            cout<<seg.prod(l,r).mn<<endl;
        }else{
            ll k=get_id(x);
            ll l=seg.min_left<all_one>(k);
            ll r=seg.max_right<all_one>(k);
            cout<<xs[r]-xs[l]+1<<endl;
        }
    }

}
0