結果
問題 | No.2292 Interval Union Find |
ユーザー |
![]() |
提出日時 | 2023-05-05 21:45:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,789 bytes |
コンパイル時間 | 4,121 ms |
コンパイル使用メモリ | 263,232 KB |
最終ジャッジ日時 | 2025-02-12 17:54:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 WA * 34 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001using P = pair<int,int>;P op(P a,P b){a.first += b.first;a.second += b.second;return a;}P e(){return make_pair(0,0);}P mapping(int a,P b){if(a==-1)return b;b.first = a * b.second;return b;}int composition(int a,int b){if(a==-1)return b;return a;}int id(){return -1;}bool check(P a){return a.first==a.second;}int main(){int n,q;cin>>n>>q;vector<int> t(q),a(q),b(q);vector<int> v;rep(i,q){cin>>t[i];if(t[i]!=4){cin>>a[i]>>b[i];v.push_back(a[i]);v.push_back(a[i]+1);v.push_back(b[i]);v.push_back(b[i]+1);}else{cin>>a[i];v.push_back(a[i]);v.push_back(a[i]+1);}}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());lazy_segtree<P,op,e,int,mapping,composition,id> seg(v.size()-1);rep(i,v.size()-1)seg.set(i,make_pair(0,v[i+1] - v[i]));rep(i,q){if(t[i]<=2){int l = distance(v.begin(),lower_bound(v.begin(),v.end(),a[i]));int r = distance(v.begin(),lower_bound(v.begin(),v.end(),b[i]));if(t[i]==1)seg.apply(l,r,1);else seg.apply(l,r,0);}if(t[i]==3){if(a[i]>b[i])swap(a[i],b[i]);int l = distance(v.begin(),lower_bound(v.begin(),v.end(),a[i]));int r = distance(v.begin(),lower_bound(v.begin(),v.end(),b[i]));if(seg.prod(l,r).first==r-l)cout<<1<<endl;else cout<<0<<endl;}if(t[i]==4){int l = distance(v.begin(),lower_bound(v.begin(),v.end(),a[i]));int r = seg.max_right<check>(l);l = seg.min_left<check>(r);cout<<v[r]-v[l]+1<<endl;}}return 0;}