結果
問題 | No.2292 Interval Union Find |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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";}}}