結果

問題 No.2292 Interval Union Find
ユーザー coindarwcoindarw
提出日時 2024-10-01 02:13:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 173 ms / 5,000 ms
コード長 4,652 bytes
コンパイル時間 3,151 ms
コンパイル使用メモリ 253,712 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-10-01 02:13:34
合計ジャッジ時間 11,983 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Range {
T l, r;
Range(T l, T r) : l(l), r(r) {
if (l > r) l = r = 0ll;
}
Range() : Range(0ll, 0ll) {}
Range operator&(Range b) const {
T nl = max(l, b.l), nr = min(r, b.r);
if (nl < nr) return Range(nl, nr);
else return Range();
}
Range operator|(Range b) const {
if (max(l, b.l) > min(r, b.r)) return Range();
return Range(min(l, b.l), max(r, b.r));
}
bool empty() const { return l == r; }
bool contains(T x) const { return l <= x && x < r; }
T count() const { return r - l; }
bool operator<(const Range& b) const { return (l != b.l) ? l < b.l : r < b.r; }
};
template <typename T>
struct RangeSet {
set<Range<T>> ranges;
RangeSet() {}
int64_t cnt = 0;
void insert(Range<T> r) {
if (r.empty()) return;
auto it = ranges.lower_bound(r);
if (it != ranges.end() && it->l == r.l && r.r <= it->r) return;
if (it != ranges.begin()) {
auto pit = prev(it);
if (r.r <= pit->r) return;
if (r.l <= pit->r) {
r.l = pit->l;
cnt -= pit->count();
ranges.erase(pit);
}
}
while (it != ranges.end() && r.r >= it->l) {
r.r = max(r.r, it->r);
cnt -= it->count();
it = ranges.erase(it);
}
cnt += r.count();
ranges.insert(r);
}
void erase(Range<T> r) {
if (r.empty()) return;
auto it = ranges.lower_bound(r);
if (it != ranges.end() && it->l == r.l && r.r <= it->r) {
Range<T> nl = Range(it->l, r.l);
Range<T> nr = Range(r.r, it->r);
cnt -= it->count();
cnt += nl.count() + nr.count();
ranges.erase(it);
if (!nl.empty()) ranges.insert(nl);
if (!nr.empty()) ranges.insert(nr);
return;
}
if (it != ranges.begin()) {
auto pit = prev(it);
if (r.r <= pit->r) {
Range<T> nl = Range(pit->l, r.l);
Range<T> nr = Range(r.r, pit->r);
cnt -= pit->count();
cnt += nl.count() + nr.count();
ranges.erase(pit);
if (!nl.empty()) ranges.insert(nl);
if (!nr.empty()) ranges.insert(nr);
return;
}
if (r.l <= pit->r) {
Range<T> nl = Range(pit->l, r.l);
cnt -= pit->count();
ranges.erase(pit);
if (!nl.empty()) ranges.insert(nl);
}
}
while (it != ranges.end() && r.r >= it->l) {
if (it->r <= r.r) {
cnt -= it->count();
it = ranges.erase(it);
} else {
Range<T> nr = Range(r.r, it->r);
cnt -= it->count();
it = ranges.erase(it);
if (!nr.empty()) ranges.insert(nr);
}
}
}
Range<T> get(T x) {
auto it = ranges.lower_bound(Range<T>(x, numeric_limits<T>::max()));
if (it != ranges.begin()) {
auto pit = prev(it);
if (pit->contains(x)) return *pit;
}
return Range<T>();
}
};
template <typename T>
struct RangeSetDisjoint {
RangeSet<T> rs;
RangeSetDisjoint() {}
void insert(Range<T> r) {
T x = r.l * 2, y = (r.r - 1) * 2;
Range r2(x, y + 1);
rs.insert(r2);
}
void erase(Range<T> r) {
T x = r.l * 2, y = (r.r - 1) * 2;
Range r2(x + 1, y);
rs.erase(r2);
}
Range<T> get(T x) {
Range<T> r = rs.get(x * 2);
if (r.empty()) return r;
return Range<T>(r.l / 2, (r.r + 1) / 2);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
RangeSetDisjoint<int> rs;
while (q--) {
int t;
cin >> t;
if (t == 1) {
int l, r;
cin >> l >> r;
rs.insert({l, r + 1});
} else if (t == 2) {
int l, r;
cin >> l >> r;
rs.erase({l, r + 1});
} else if (t == 3) {
int u, v;
cin >> u >> v;
if (u == v) {
cout << 1 << "\n";
continue;
}
auto r = rs.get(u);
cout << r.contains(v) << "\n";
} else {
int v;
cin >> v;
auto r = rs.get(v);
cout << max(1, r.count()) << "\n";
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0