cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: データ構造/区間を std::set で管理するやつ
(test/data_structure/intervals_managed_by_set.test.cpp)

Depends on

Code

/*
 * @title データ構造/区間を std::set で管理するやつ
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2880
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

#include "emthrm/data_structure/intervals_managed_by_set.hpp"

int main() {
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<int> d(m), a(m), b(m), e(q), s(q), t(q);
  for (int i = 0; i < m; ++i) {
    std::cin >> d[i] >> a[i] >> b[i];
  }
  for (int i = 0; i < q; ++i) {
    std::cin >> e[i] >> s[i] >> t[i];
  }
  std::vector<int> order(m + q);
  std::iota(order.begin(), order.end(), 0);
  std::sort(order.begin(), order.end(), [m, &d, &e](const int a, const int b) {
    const int t_a = (a < m ? d[a] : e[a - m]), t_b = (b < m ? d[b] : e[b - m]);
    return t_a != t_b ? t_a < t_b : (a < m) < (b < m);
  });
  std::vector<bool> ans(q, false);
  emthrm::IntervalsManagedBySet<int> intervals;
  for (int i : order) {
    if (i < m) {
      intervals.insert(a[i], b[i] - 1);
    } else {
      i -= m;
      ans[i] = s[i] >= t[i] || intervals.contains(s[i], t[i] - 1);
    }
  }
  for (int i = 0; i < q; ++i) {
    std::cout << (ans[i] ? "Yes\n" : "No\n");
  }
  return 0;
}
#line 1 "test/data_structure/intervals_managed_by_set.test.cpp"
/*
 * @title データ構造/区間を std::set で管理するやつ
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2880
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

#line 1 "include/emthrm/data_structure/intervals_managed_by_set.hpp"



#include <cassert>
#line 6 "include/emthrm/data_structure/intervals_managed_by_set.hpp"
#include <iterator>
#include <limits>
#include <set>
#include <utility>

namespace emthrm {

template <typename T>
struct IntervalsManagedBySet {
  using IntervalsType = std::set<std::pair<T, T>>;
  IntervalsType intervals{
      {std::numeric_limits<T>::lowest(), std::numeric_limits<T>::lowest()},
      {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}};

  IntervalsManagedBySet() = default;

  bool contains(const T x) const { return contains(x, x); }

  bool contains(const T left, const T right) const {
    return find(left, right) != intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> erase(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) {
      const T right = it->second;
      it = intervals.erase(it);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    } else {
      it = std::prev(it);
      const auto [left, right] = *it;
      if (right < x) return {std::next(it), false};
      intervals.erase(it);
      it = std::next(intervals.emplace(left, x - 1).first);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    }
    return {it, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> erase(
      const T left, const T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    T res = 0;
    for (; it->second <= right; it = intervals.erase(it)) {
      res += it->second - it->first + 1;
    }
    if (it->first <= right) {
      res += right - it->first + 1;
      const T r = it->second;
      intervals.erase(it);
      it = intervals.emplace(right + 1, r).first;
    }
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      const auto [l, r] = *it;
      intervals.erase(it);
      if (right < r) {
        res += right - left + 1;
        intervals.emplace(right + 1, r);
      } else {
        res += r - left + 1;
      }
      it = std::next(intervals.emplace(l, left - 1).first);
    }
    return {it, res};
  }

  typename IntervalsType::const_iterator find(const T x) const {
    return find(x, x);
  }

  typename IntervalsType::const_iterator find(
      const T left, const T right) const {
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left < it->first) it = std::prev(it);
    return it->first <= left && right <= it->second ? it : intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> insert(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) return {it, false};
    if (x <= std::prev(it)->second) return {std::prev(it), false};
    T left = x, right = x;
    if (x + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == x - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> insert(T left, T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      left = it->first;
    }
    T res = 0;
    if (left == it->first && right <= it->second) return {it, res};
    for (; it->second <= right; it = intervals.erase(it)) {
      res -= it->second - it->first + 1;
    }
    if (it->first <= right) {
      res -= it->second - it->first + 1;
      right = it->second;
      it = intervals.erase(it);
    }
    res += right - left + 1;
    if (right + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == left - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, res};
  }

  T mex(const T x = 0) const {
    auto it = intervals.lower_bound({x, x});
    if (x <= std::prev(it)->second) it = std::prev(it);
    return x < it->first ? x : it->second + 1;
  }

  friend std::ostream& operator<<(std::ostream& os,
                                  const IntervalsManagedBySet& x) {
    if (x.intervals.size() == 2) return os;
    auto it = next(x.intervals.begin());
    while (true) {
      os << '[' << it->first << ", " << it->second << ']';
      it = next(it);
      if (next(it) == x.intervals.end()) break;
      os << ' ';
    }
    return os;
  }
};

}  // namespace emthrm


#line 13 "test/data_structure/intervals_managed_by_set.test.cpp"

int main() {
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<int> d(m), a(m), b(m), e(q), s(q), t(q);
  for (int i = 0; i < m; ++i) {
    std::cin >> d[i] >> a[i] >> b[i];
  }
  for (int i = 0; i < q; ++i) {
    std::cin >> e[i] >> s[i] >> t[i];
  }
  std::vector<int> order(m + q);
  std::iota(order.begin(), order.end(), 0);
  std::sort(order.begin(), order.end(), [m, &d, &e](const int a, const int b) {
    const int t_a = (a < m ? d[a] : e[a - m]), t_b = (b < m ? d[b] : e[b - m]);
    return t_a != t_b ? t_a < t_b : (a < m) < (b < m);
  });
  std::vector<bool> ans(q, false);
  emthrm::IntervalsManagedBySet<int> intervals;
  for (int i : order) {
    if (i < m) {
      intervals.insert(a[i], b[i] - 1);
    } else {
      i -= m;
      ans[i] = s[i] >= t[i] || intervals.contains(s[i], t[i] - 1);
    }
  }
  for (int i = 0; i < q; ++i) {
    std::cout << (ans[i] ? "Yes\n" : "No\n");
  }
  return 0;
}
Back to top page