C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }