結果
問題 | No.2292 Interval Union Find |
ユーザー |
![]() |
提出日時 | 2023-05-06 03:24:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 5,000 ms |
コード長 | 7,128 bytes |
コンパイル時間 | 1,818 ms |
コンパイル使用メモリ | 204,844 KB |
最終ジャッジ日時 | 2025-02-12 20:23:23 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct iofast_t {iofast_t() {ios::sync_with_stdio(false);cin.tie(nullptr);}} iofast;struct uns_t {} uns;template <typename Element, typename Head, typename ...Args>auto vec(Element init, Head arg, Args ...args) {if constexpr (sizeof...(Args) == 0) return vector(arg, init);else return vector(arg, vec(init, args...));}template <typename Element, typename Head, typename ...Args>auto vec(uns_t, Head arg, Args ...args) {return vec(Element(), arg, args...);}template <typename Container>auto distance(const Container &c, decltype(begin(c)) iter) {return distance(begin(c), iter);}template <typename RIter, typename Compare = less<typename iterator_traits<RIter>::value_type>>auto isort(RIter first, RIter last, Compare comp = Compare()) {vector<int> i(distance(first, last));iota(begin(i), end(i), 0);sort(begin(i), end(i), [&](auto x, auto y) {return comp(*(first + x), *(first + y));});return i;}template <typename, template <typename> typename, typename = void_t<>>struct detect : false_type {};template <typename T, template <typename> typename Check>struct detect<T, Check, void_t<Check<T>>> : true_type {};template <typename T, template <typename> typename Check>constexpr inline bool detect_v = detect<T, Check>::value;template <typename T>using has_member_sort = decltype(declval<T>().sort());template <typename Container, typename Compare = less<typename Container::value_type>>auto sorted(Container c, Compare comp = Compare()) {if constexpr (detect_v<Container, has_member_sort>) {c.sort(comp);return c;}else {sort(begin(c), end(c), comp);return c;}}template <typename Container, typename Compare = equal_to<typename Container::value_type>>auto uniqued(Container c, Compare comp = Compare()) {c.erase(unique(begin(c), end(c), comp), end(c));return c;}template <typename T, typename Compare = less<T>>T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }template <typename T, typename Compare = less<T>>T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }template <typename F>constexpr auto fix(F &&f) noexcept {return [f = std::tuple<F>(std::forward<F>(f))](auto &&...args) mutable {return std::get<0>(f)(fix(std::get<0>(f)), std::forward<decltype(args)>(args)...);};}// 互いに重ならない区間の集合 { [l1, r1), [l2, r2), ... } を管理する (li < ri)template <typename Int>struct segment_set {using int_type = Int;segment_set(): seg_() {}public:// 区間 [l, r) を追加する// 既存要素と重なる部分はマージする (境界の接合は行わない)void insert(int_type l, int_type r) {assert(l <= r);if (l == r) {return;}auto iter1 = seg_.upper_bound(l);auto iter2 = seg_.lower_bound(r);if (iter1 != std::begin(seg_)) {std::advance(iter1, -1);if (l < iter1->second) {l = iter1->first;}std::advance(iter1, +1);}if (iter2 != std::begin(seg_)) {std::advance(iter2, -1);if (r <= iter2->second) {r = iter2->second;}std::advance(iter2, +1);}seg_.erase(iter1, iter2);seg_[l] = r;}// 区間 [l, r) を追加する// clear(l, r) -> insert(l, r)void overwrite(int_type l, int_type r) {assert(l <= r);if (l == r) {return;}clear(l, r);seg_[l] = r;}// 要素 [x, k), [k, y) を [x, y) へマージするvoid connect(int_type k) {auto iter1 = seg_.lower_bound(k);if (iter1 == std::begin(seg_) || iter1 == std::end(seg_)) {return;}auto iter2 = std::prev(iter1);auto [l1, r1] = *iter2;auto [l2, r2] = *iter1;if (r1 == k && l2 == k) {seg_.erase(iter1);seg_.erase(iter2);seg_[l1] = r2;}}// 要素 [x, y) を [x, k), [k, y) に分割void split(int_type k) {auto _ = wrapped(k);if (!_.has_value()) {return;}auto [l, r] = *_;seg_.erase(l);seg_[l] = k;seg_[k] = r;}// 集合から [l, r) に重なる部分を *切り取り* 削除する// 部分的に重なるような区間要素に対しては適切な分割が行われるvoid clear(int_type l, int_type r) {assert(l <= r);split(l);split(r);remove_covered(l, r);}// [l, r) に重なる区間を集合からすべて取り除くvoid remove_covered(int_type l, int_type r) {assert(l <= r);auto iter = seg_.upper_bound(l);if (iter != std::begin(seg_)) {std::advance(iter, -1);}while (iter != std::end(seg_) && iter->first < r) {if (l < iter->second) {iter = seg_.erase(iter);}else {std::advance(iter, +1);}}}// 存在するのなら l <= k < r な区間 [l, r) を返すstd::optional<std::pair<int_type, int_type>> wrapped(int_type k) const {auto iter = seg_.upper_bound(k);if (iter == std::begin(seg_)) {return std::nullopt;}std::advance(iter, -1);if (iter->second <= k) {return std::nullopt;}return *iter;}// k を含む区間のサイズを取得するstd::size_t wrapped_size(int_type k) const {auto _ = wrapped(k);if (!_.has_value()) {return 0;}auto [l, r] = *_;return r - l;}// k を含む区間が存在するかbool is_wrapped(int_type k) const {return wrapped(k).has_value();}// x, y が同じ区間に属するかbool same(int_type x, int_type y) const {auto _ = wrapped(x);if (!_.has_value()) {return false;}auto [l, r] = *_;return l <= y && y < r;}private:std::map<int_type, int_type> seg_;};int main() {int n, q; cin >> n >> q;segment_set<int64_t> set;while (q--) {int t; cin >> t;if (t == 1) {int l, r; cin >> l >> r; ++r;set.insert(l, r);}if (t == 2) {int l, r; cin >> l >> r;set.clear(l + 1, r);}if (t == 3) {int u, v; cin >> u >> v;if (u != v) {cout << set.same(u, v) << '\n';}else {cout << 1 << '\n';}}if (t == 4) {int u; cin >> u;cout << max<int64_t>(1, set.wrapped_size(u)) << '\n';}}cout << flush;}