tests/real_interval_set.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2880

Depends on

• tools/detail/interval_set.hpp
• std::less by key (tools/less_by.hpp)
• Set of real numbers as closed integer intervals (tools/real_interval_set.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2880

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include "tools/real_interval_set.hpp"
#include "tools/less_by.hpp"

using ll = long long;

struct query {
  ll query_type;
  ll id;
  ll day;
  ll from;
  ll to;
  query(ll query_type, ll id, ll day, ll from, ll to) :
    query_type(query_type),
    id(id),
    day(day),
    from(from),
    to(to) {
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, M, Q;
  std::cin >> N >> M >> Q;

  std::vector<query> queries;
  for (ll i = 0; i < M; ++i) {
    ll D, A, B;
    std::cin >> D >> A >> B;
    queries.emplace_back(1, i, D, A, B);
  }
  for (ll i = 0; i < Q; ++i) {
    ll E, S, T;
    std::cin >> E >> S >> T;
    queries.emplace_back(0, i, E, S, T);
  }

  std::sort(queries.begin(), queries.end(), tools::less_by([](const query& q) {
    return std::make_pair(q.day, q.query_type);
  }));

  tools::real_interval_set<ll> set;
  std::vector<bool> answers(Q);
  for (const query& query : queries) {
    if (query.query_type == 0) {
      const auto it = set.find(query.from);
      const ll reachable = it != set.end() ? it->second : query.from;
      answers[query.id] = query.to <= reachable;
    } else {
      set.insert(query.from, query.to);
    }
  }

  for (const bool answer : answers) {
    std::cout << (answer ? "Yes" : "No") << '\n';
  }

  return 0;
}

#line 1 "tests/real_interval_set.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2880

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#line 1 "tools/real_interval_set.hpp"



#line 1 "tools/detail/interval_set.hpp"



#include <map>
#include <iterator>
#include <optional>
#line 9 "tools/detail/interval_set.hpp"
#include <string>

namespace tools {
  namespace detail {
    template <typename T, bool Mergeable>
    class interval_set {
    private:
      // closed intervals
      ::std::map<T, T> m_intervals;
  
    public:
      interval_set() = default;
      interval_set(const ::tools::detail::interval_set<T, Mergeable>&) = default;
      interval_set(::tools::detail::interval_set<T, Mergeable>&&) = default;
      ~interval_set() = default;
      ::tools::detail::interval_set<T, Mergeable>& operator=(const ::tools::detail::interval_set<T, Mergeable>&) = default;
      ::tools::detail::interval_set<T, Mergeable>& operator=(::tools::detail::interval_set<T, Mergeable>&&) = default;
  
      auto begin() const {
        return this->m_intervals.begin();
      }
  
      auto end() const {
        return this->m_intervals.end();
      }
  
      bool empty() const {
        return this->m_intervals.empty();
      }
  
      auto size() const {
        return this->m_intervals.size();
      }
  
      auto find(const T& x) const {
        const auto next = this->m_intervals.upper_bound(x);
        if (next == this->m_intervals.begin()) return this->m_intervals.end();
        const auto prev = ::std::prev(next);
        if (prev->second < x) return this->m_intervals.end();
        return prev;
      }
  
      bool contains(const T& x) const {
        return this->find(x) != this->m_intervals.end();
      }
  
      auto lower_bound(const T& x) const {
        const auto next = this->m_intervals.lower_bound(x);
        if (next == this->m_intervals.begin()) return next;
        const auto prev = ::std::prev(next);
        if (prev->second < x) return next;
        return prev;
      }
  
      auto upper_bound(const T& x) const {
        return this->m_intervals.upper_bound(x);
      }
  
      void insert(const T& l, const T& r) {
        if (!(l <= r)) {
          return;
        }
  
        const auto l_it = this->find(l - (Mergeable ? 1 : 0));
        const T min = l_it != this->m_intervals.end() ? l_it->first : l;
        const auto r_it = this->find(r + (Mergeable ? 1 : 0));
        const T max = r_it != this->m_intervals.end() ? r_it->second : r;
  
        this->m_intervals.erase(this->lower_bound(l - (Mergeable ? 1 : 0)), this->upper_bound(r + (Mergeable ? 1 : 0)));
        this->m_intervals.emplace(min, max);
      }
  
      void erase(const T& l, const T& r) {
        if (!(l <= r + (Mergeable ? 0 : 1))) {
          return;
        }
  
        const auto l_it = this->find(l);
        const auto l_new_interval = l_it != this->m_intervals.end() && l_it->first <= l - (Mergeable ? 1 : 0)
          ? ::std::make_optional(::std::make_pair(l_it->first, l - (Mergeable ? 1 : 0)))
          : ::std::nullopt;
        const auto r_it = this->find(r);
        const auto r_new_interval = r_it != this->m_intervals.end() && r + (Mergeable ? 1 : 0) <= r_it->second
          ? ::std::make_optional(::std::make_pair(r + (Mergeable ? 1 : 0), r_it->second))
          : ::std::nullopt;
  
        this->m_intervals.erase(this->lower_bound(l), this->upper_bound(r));
  
        if (l_new_interval) {
          this->m_intervals.emplace(l_new_interval->first, l_new_interval->second);
        }
        if (r_new_interval) {
          this->m_intervals.emplace(r_new_interval->first, r_new_interval->second);
        }
      }
  
      friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::detail::interval_set<T, Mergeable>& self) {
        os << '{';
        ::std::string delimiter = "";
        for (const auto& [l, r] : self) {
          os << delimiter << '[' << l << ", " << r << ']';
          delimiter = ", ";
        }
        os << '}';
        return os;
      }
    };
  }
}


#line 5 "tools/real_interval_set.hpp"

namespace tools {
  template <typename T>
  using real_interval_set = ::tools::detail::interval_set<T, false>;
}


#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 9 "tests/real_interval_set.test.cpp"

using ll = long long;

struct query {
  ll query_type;
  ll id;
  ll day;
  ll from;
  ll to;
  query(ll query_type, ll id, ll day, ll from, ll to) :
    query_type(query_type),
    id(id),
    day(day),
    from(from),
    to(to) {
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, M, Q;
  std::cin >> N >> M >> Q;

  std::vector<query> queries;
  for (ll i = 0; i < M; ++i) {
    ll D, A, B;
    std::cin >> D >> A >> B;
    queries.emplace_back(1, i, D, A, B);
  }
  for (ll i = 0; i < Q; ++i) {
    ll E, S, T;
    std::cin >> E >> S >> T;
    queries.emplace_back(0, i, E, S, T);
  }

  std::sort(queries.begin(), queries.end(), tools::less_by([](const query& q) {
    return std::make_pair(q.day, q.query_type);
  }));

  tools::real_interval_set<ll> set;
  std::vector<bool> answers(Q);
  for (const query& query : queries) {
    if (query.query_type == 0) {
      const auto it = set.find(query.from);
      const ll reachable = it != set.end() ? it->second : query.from;
      answers[query.id] = query.to <= reachable;
    } else {
      set.insert(query.from, query.to);
    }
  }

  for (const bool answer : answers) {
    std::cout << (answer ? "Yes" : "No") << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	00_sample_01.in	AC	5 ms	4 MB
g++	10_handmade_00.in	AC	5 ms	4 MB
g++	10_handmade_01.in	AC	5 ms	4 MB
g++	10_handmade_02.in	AC	4 ms	4 MB
g++	10_handmade_03.in	AC	5 ms	4 MB
g++	50_random_small_00.in	AC	5 ms	4 MB
g++	50_random_small_01.in	AC	5 ms	4 MB
g++	50_random_small_02.in	AC	4 ms	4 MB
g++	50_random_small_03.in	AC	4 ms	4 MB
g++	50_random_small_04.in	AC	4 ms	4 MB
g++	50_random_small_05.in	AC	4 ms	4 MB
g++	50_random_small_06.in	AC	4 ms	4 MB
g++	50_random_small_07.in	AC	4 ms	4 MB
g++	50_random_small_08.in	AC	4 ms	4 MB
g++	50_random_small_09.in	AC	4 ms	4 MB
g++	51_random_large_00.in	AC	37 ms	9 MB
g++	51_random_large_01.in	AC	30 ms	10 MB
g++	51_random_large_02.in	AC	31 ms	9 MB
g++	51_random_large_03.in	AC	49 ms	15 MB
g++	51_random_large_04.in	AC	38 ms	9 MB
g++	51_random_large_05.in	AC	53 ms	15 MB
g++	51_random_large_06.in	AC	33 ms	9 MB
g++	51_random_large_07.in	AC	32 ms	10 MB
g++	51_random_large_08.in	AC	38 ms	9 MB
g++	51_random_large_09.in	AC	31 ms	9 MB
g++	52_MIN_00.in	AC	5 ms	4 MB
g++	53_MAX_00.in	AC	60 ms	14 MB
g++	53_MAX_01.in	AC	60 ms	15 MB
g++	53_MAX_02.in	AC	60 ms	14 MB
g++	53_MAX_03.in	AC	60 ms	16 MB
g++	53_MAX_04.in	AC	61 ms	14 MB
g++	53_MAX_05.in	AC	61 ms	16 MB
g++	53_MAX_06.in	AC	61 ms	15 MB
g++	53_MAX_07.in	AC	62 ms	14 MB
g++	53_MAX_08.in	AC	60 ms	14 MB
g++	53_MAX_09.in	AC	60 ms	15 MB
g++	54_Nsmall_00.in	AC	42 ms	14 MB
g++	54_Nsmall_01.in	AC	31 ms	9 MB
g++	54_Nsmall_02.in	AC	45 ms	15 MB
g++	54_Nsmall_03.in	AC	21 ms	7 MB
g++	54_Nsmall_04.in	AC	43 ms	16 MB
g++	54_Nsmall_05.in	AC	12 ms	5 MB
g++	54_Nsmall_06.in	AC	20 ms	6 MB
g++	54_Nsmall_07.in	AC	27 ms	9 MB
g++	54_Nsmall_08.in	AC	39 ms	9 MB
g++	54_Nsmall_09.in	AC	36 ms	9 MB
g++	55_Msmall_00.in	AC	8 ms	4 MB
g++	55_Msmall_01.in	AC	20 ms	6 MB
g++	55_Msmall_02.in	AC	8 ms	4 MB
g++	55_Msmall_03.in	AC	15 ms	6 MB
g++	55_Msmall_04.in	AC	12 ms	5 MB
g++	55_Msmall_05.in	AC	16 ms	7 MB
g++	55_Msmall_06.in	AC	17 ms	6 MB
g++	55_Msmall_07.in	AC	13 ms	5 MB
g++	55_Msmall_08.in	AC	20 ms	6 MB
g++	55_Msmall_09.in	AC	17 ms	6 MB
g++	56_DEsmall_00.in	AC	33 ms	9 MB
g++	56_DEsmall_01.in	AC	50 ms	15 MB
g++	56_DEsmall_02.in	AC	41 ms	15 MB
g++	56_DEsmall_03.in	AC	32 ms	10 MB
g++	56_DEsmall_04.in	AC	24 ms	9 MB
g++	56_DEsmall_05.in	AC	27 ms	10 MB
g++	56_DEsmall_06.in	AC	31 ms	9 MB
g++	56_DEsmall_07.in	AC	30 ms	10 MB
g++	56_DEsmall_08.in	AC	12 ms	5 MB
g++	56_DEsmall_09.in	AC	24 ms	9 MB
g++	60_challenge_00.in	AC	57 ms	15 MB
g++	60_challenge_01.in	AC	85 ms	15 MB

Back to top page