This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc254/tasks/abc254_g" #include <iostream> #include "library/datastructure/util/range_set.hpp" #include "library/graph/functional_graph.hpp" #include "library/util/coordinate_compressor.hpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, q; std::cin >> n >> m >> q; std::vector<suisen::RangeSet<int, false>> range_sets(n); for (int i = 0; i < m; ++i) { int a, b, c; std::cin >> a >> b >> c; --a, --b, --c; range_sets[a].insert(b, c); } suisen::CoordinateCompressorBuilder<int> comp_builder; std::vector<std::tuple<int, int, int, int>> queries(q); for (auto& [x, y, z, w] : queries) { std::cin >> x >> y >> z >> w; --x, --y, --z, --w; if (y > w) std::swap(x, z), std::swap(y, w); comp_builder.push(y); } std::vector<std::pair<int, int>> ranges; for (const auto& st : range_sets) for (const auto& [l, r] : st) { ranges.emplace_back(l, r); comp_builder.push(r); } std::sort(ranges.begin(), ranges.end()); const int range_num = ranges.size(); const auto comp = comp_builder.build(); const int k = comp.size(); suisen::FunctionalGraph g(k); { int i = 0, max_r = -1; for (int j = 0; j < k; ++j) { const int pos = comp.decomp(j); while (i < range_num and ranges[i].first <= pos) max_r = std::max(max_r, ranges[i++].second); g[j] = max_r < pos ? j : comp[max_r]; } } const auto doubling = g.doubling(range_num); for (auto& [x, y, z, w] : queries) { const int ans = w - y; if (const auto itx = range_sets[x].find_range(y); itx != range_sets[x].end()) y = itx->second; if (const auto itz = range_sets[z].find_range(w); itz != range_sets[z].end()) w = itz->first; if (y >= w) { std::cout << ans + (x != z) << '\n'; } else { const int w_ = w; const auto opt_res = doubling.step_until(comp[y], [&](int v) { return comp.decomp(v) >= w_; }); std::cout << (opt_res.has_value() ? ans + opt_res->step + 1 : -1) << '\n'; } } return 0; }
#line 1 "test/src/graph/functional_graph/abc254_g.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc254/tasks/abc254_g" #include <iostream> #line 1 "library/datastructure/util/range_set.hpp" #include <map> namespace suisen { template <typename T, bool merge_adjacent_segment = true> struct RangeSet : public std::map<T, T> { public: RangeSet() : _size(0) {} // returns the number of intergers in this set (not the number of ranges). O(1) T size() const { return number_of_elements(); } // returns the number of intergers in this set (not the number of ranges). O(1) T number_of_elements() const { return _size; } // returns the number of ranges in this set (not the number of integers). O(1) int number_of_ranges() const { return std::map<T, T>::size(); } // returns whether the given integer is in this set or not. O(log N) bool contains(T x) const { auto it = this->upper_bound(x); return it != this->begin() and x <= std::prev(it)->second; } /** * returns the iterator pointing to the range [l, r] in this set s.t. l <= x <= r. * if such a range does not exist, returns `end()`. * O(log N) */ auto find_range(T x) const { auto it = this->upper_bound(x); return it != this->begin() and x <= (--it)->second ? it : this->end(); } // returns whether `x` and `y` is in this set and in the same range. O(log N) bool in_the_same_range(T x, T y) const { auto it = get_containing_range(x); return it != this->end() and it->first <= y and y <= it->second; } // inserts the range [x, x] and returns the number of integers inserted to this set. O(log N) T insert(T x) { return insert(x, x); } // inserts the range [l, r] and returns the number of integers inserted to this set. amortized O(log N) T insert(T l, T r) { if (l > r) return 0; auto it = this->upper_bound(l); if (it != this->begin() and is_mergeable(std::prev(it)->second, l)) { it = std::prev(it); l = std::min(l, it->first); } T inserted = 0; for (; it != this->end() and is_mergeable(r, it->first); it = std::map<T, T>::erase(it)) { auto [cl, cr] = *it; r = std::max(r, cr); inserted -= cr - cl + 1; } inserted += r - l + 1; (*this)[l] = r; _size += inserted; return inserted; } // erases the range [x, x] and returns the number of intergers erased from this set. O(log N) T erase(T x) { return erase(x, x); } // erases the range [l, r] and returns the number of intergers erased from this set. amortized O(log N) T erase(T l, T r) { if (l > r) return 0; T tl = l, tr = r; auto it = this->upper_bound(l); if (it != this->begin() and l <= std::prev(it)->second) { it = std::prev(it); tl = it->first; } T erased = 0; for (; it != this->end() and it->first <= r; it = std::map<T, T>::erase(it)) { auto [cl, cr] = *it; tr = cr; erased += cr - cl + 1; } if (tl < l) { (*this)[tl] = l - 1; erased -= l - tl; } if (r < tr) { (*this)[r + 1] = tr; erased -= tr - r; } _size -= erased; return erased; } // returns minimum integer x s.t. x >= lower and x is NOT in this set T minimum_excluded(T lower = 0) const { static_assert(merge_adjacent_segment); auto it = find_range(lower); return it == this->end() ? lower : it->second + 1; } // returns maximum integer x s.t. x <= upper and x is NOT in this set T maximum_excluded(T upper) const { static_assert(merge_adjacent_segment); auto it = find_range(upper); return it == this->end() ? upper : it->first - 1; } private: T _size; bool is_mergeable(T cur_r, T next_l) { return next_l <= cur_r + merge_adjacent_segment; } }; } // namespace suisen #line 1 "library/graph/functional_graph.hpp" #include <cassert> #include <cstdint> #include <optional> #include <tuple> #include <utility> #include <vector> namespace suisen { struct FunctionalGraph { struct Doubling; template <typename T, T(*)(T, T), T(*)()> struct DoublingSum; friend struct Doubling; template <typename T, T(*op)(T, T), T(*e)()> friend struct DoublingSum; FunctionalGraph() : FunctionalGraph(0) {} FunctionalGraph(int n) : _n(n), _nxt(n) {} FunctionalGraph(const std::vector<int>& nxt) : _n(nxt.size()), _nxt(nxt) {} const int& operator[](int u) const { return _nxt[u]; } int& operator[](int u) { return _nxt[u]; } struct Doubling { friend struct FunctionalGraph; int query(int u, long long d) const { for (int l = _log; l >= 0; --l) if ((d >> l) & 1) u = _nxt[l][u]; return u; } struct BinarySearchResult { int v; long long step; operator std::pair<int, long long>() const { return std::pair<int, long long>{ v, step }; } }; template <typename Pred> auto max_step(int u, Pred &&f) const { assert(f(u)); long long step = 0; for (int l = _log; l >= 0; --l) if (int nxt_u = _nxt[l][u]; f(nxt_u)) { u = nxt_u, step |= 1LL << l; } return BinarySearchResult{ u, step }; } template <typename Pred> std::optional<BinarySearchResult> step_until(int u, Pred &&f) const { if (f(u)) return BinarySearchResult { u, 0 }; auto [v, step] = max_step(u, [&](int v) { return not f(v); }); v = _nxt[0][v], ++step; if (not f(v)) return std::nullopt; return BinarySearchResult{ v, step }; } private: int _n, _log; std::vector<std::vector<int>> _nxt; Doubling(const std::vector<int>& nxt, long long max_step) : _n(nxt.size()), _log(floor_log2(max_step)), _nxt(_log + 1, std::vector<int>(_n)) { _nxt[0] = nxt; for (int i = 1; i <= _log; ++i) for (int j = 0; j < _n; ++j) { _nxt[i][j] = _nxt[i - 1][_nxt[i - 1][j]]; } } }; template <typename T, T(*op)(T, T), T(*e)()> struct DoublingSum : private Doubling { friend struct FunctionalGraph; struct Result { int v; T sum; operator std::pair<int, T>() const { return std::pair<int, T>{ v, sum }; } }; auto query(int u, long long d) const { T sum = e(); for (int l = _log; l >= 0; --l) if ((d >> l) & 1) sum = op(sum, _dat[l][std::exchange(u, _nxt[l][u])]); return Result{ u, sum }; } struct BinarySearchResult { int v; T sum; long long step; operator std::tuple<int, T, long long>() const { return std::tuple<int, T, long long>{ v, sum, step }; } }; template <typename Pred> auto max_step(int u, Pred &&f) const { assert(f(e())); long long step = 0; T sum = e(); for (int l = _log; l >= 0; --l) { if (T nxt_sum = op(sum, _dat[l][u]); f(nxt_sum)) { sum = std::move(nxt_sum), u = _nxt[l][u], step |= 1LL << l; } } return BinarySearchResult{ u, sum, step }; } template <typename Pred> std::optional<BinarySearchResult> step_until(int u, Pred &&f) const { if (f(e())) return BinarySearchResult { u, e(), 0 }; auto [v, sum, step] = max_step(u, [&](const T& v) { return not f(v); }); sum = op(sum, _dat[0][v]), v = _nxt[0][v], ++step; if (not f(sum)) return std::nullopt; return BinarySearchResult{ v, sum, step }; } private: std::vector<std::vector<T>> _dat; DoublingSum(const std::vector<int>& nxt, long long max_step, const std::vector<T>& dat) : Doubling(nxt, max_step), _dat(_log + 1, std::vector<T>(_n, e())) { _dat[0] = dat; for (int i = 1; i <= _log; ++i) for (int j = 0; j < _n; ++j) { _dat[i][j] = op(_dat[i - 1][j], _dat[i - 1][_nxt[i - 1][j]]); } } }; Doubling doubling(long long max_step) const { return Doubling(_nxt, max_step); } template <typename T, T(*op)(T, T), T(*e)()> DoublingSum<T, op, e> doubling(long long max_step, const std::vector<T>& dat) const { return DoublingSum<T, op, e>(_nxt, max_step, dat); } struct InfinitePath { int head_v; int head_len; int loop_v; int loop_len; InfinitePath() = default; InfinitePath(int head_v, int head_len, int loop_v, int loop_len) : head_v(head_v), head_len(head_len), loop_v(loop_v), loop_len(loop_len) {} }; std::vector<InfinitePath> infinite_paths() const { std::vector<InfinitePath> res(_n); std::vector<int> vis(_n, _n); std::vector<int> dep(_n, 0); int time = 0; auto dfs = [&](auto dfs, int u) -> int { vis[u] = time; int v = _nxt[u]; if (vis[v] == vis[u]) { // found cycle int loop_len = dep[u] - dep[v] + 1; res[u] = { u, 0, u, loop_len }; return loop_len - 1; } else if (vis[v] < vis[u]) { res[u] = { u, res[v].head_len + 1, res[v].loop_v, res[v].loop_len }; return 0; } else { dep[v] = dep[u] + 1; int c = dfs(dfs, v); if (c > 0) { // in cycle res[u] = { u, 0, u, res[v].loop_len }; return c - 1; } else { // out of cycle res[u] = { u, res[v].head_len + 1, res[v].loop_v, res[v].loop_len }; return 0; } } }; for (int i = 0; i < _n; ++i, ++time) if (vis[i] == _n) dfs(dfs, i); return res; } /** * Calculates k'th iterate: f(f(f(...f(i)))) for all 0 <= i < N in O(N) time. * Reference: https://noshi91.hatenablog.com/entry/2019/09/22/114149 */ std::vector<int> kth_iterate(const long long k) const { assert(k >= 0); std::vector<int> res(_n); std::vector<int> forest_roots; std::vector<std::vector<int>> forest(_n); std::vector<std::vector<std::pair<long long, int>>> qs(_n); for (const auto& path : infinite_paths()) { const int v = path.head_v; (path.head_len == 0 ? forest_roots : forest[_nxt[v]]).push_back(v); if (path.head_len >= k) continue; qs[path.loop_v].emplace_back(k - path.head_len, v); } std::vector<int> dfs_path(_n); auto dfs = [&](auto dfs, int u, int d) -> void { dfs_path[d] = u; if (d >= k) res[u] = dfs_path[d - k]; for (int v : forest[u]) dfs(dfs, v, d + 1); }; for (int root : forest_roots) dfs(dfs, root, 0); std::vector<int8_t> seen(_n, false); for (int root : forest_roots) { if (seen[root]) continue; std::vector<int> cycle{ root }; for (int v = _nxt[root]; v != root; v = _nxt[v]) cycle.push_back(v); const int len = cycle.size(); for (int i = 0; i < len; ++i) { const int s = cycle[i]; seen[s] = true; for (const auto& [rem, res_index] : qs[s]) { res[res_index] = cycle[(i + rem) % len]; } } } return res; } private: int _n; std::vector<int> _nxt; static int floor_log2(long long v) { int l = 0; while (1LL << (l + 1) <= v) ++l; return l; } }; } // namespace suisen #line 1 "library/util/coordinate_compressor.hpp" #include <algorithm> #line 7 "library/util/coordinate_compressor.hpp" #line 1 "library/type_traits/type_traits.hpp" #include <limits> #line 6 "library/type_traits/type_traits.hpp" #include <type_traits> namespace suisen { template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>; template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; }; template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; }; template <typename T> static constexpr int bitnum_v = bitnum<T>::value; template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; }; template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value; template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; }; template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type; template <typename T, typename = void> struct rec_value_type { using type = T; }; template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> { using type = typename rec_value_type<typename T::value_type>::type; }; template <typename T> using rec_value_type_t = typename rec_value_type<T>::type; template <typename T> class is_iterable { template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T> class is_writable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_writable_v = is_writable<T>::value; template <typename T> class is_readable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_readable_v = is_readable<T>::value; } // namespace suisen #line 9 "library/util/coordinate_compressor.hpp" namespace suisen { template <typename T> class CoordinateCompressorBuilder { public: struct Compressor { public: static constexpr int absent = -1; // default constructor Compressor() : _xs(std::vector<T>{}) {} // Construct from strictly sorted vector Compressor(const std::vector<T> &xs) : _xs(xs) { assert(is_strictly_sorted(xs)); } // Return the number of distinct keys. int size() const { return _xs.size(); } // Check if the element is registered. bool has_key(const T &e) const { return std::binary_search(_xs.begin(), _xs.end(), e); } // Compress the element. if not registered, returns `default_value`. (default: Compressor::absent) int comp(const T &e, int default_value = absent) const { const int res = min_geq_index(e); return res != size() and _xs[res] == e ? res : default_value; } // Restore the element from the index. T decomp(const int compressed_index) const { return _xs[compressed_index]; } // Compress the element. Equivalent to call `comp(e)` int operator[](const T &e) const { return comp(e); } // Return the minimum registered value greater than `e`. if not exists, return `default_value`. T min_gt(const T &e, const T &default_value) const { auto it = std::upper_bound(_xs.begin(), _xs.end(), e); return it == _xs.end() ? default_value : *it; } // Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`. T min_geq(const T &e, const T &default_value) const { auto it = std::lower_bound(_xs.begin(), _xs.end(), e); return it == _xs.end() ? default_value : *it; } // Return the maximum registered value less than `e`. if not exists, return `default_value` T max_lt(const T &e, const T &default_value) const { auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>()); return it == _xs.rend() ? default_value : *it; } // Return the maximum registered value less than or equal to `e`. if not exists, return `default_value` T max_leq(const T &e, const T &default_value) const { auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>()); return it == _xs.rend() ? default_value : *it; } // Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`. int min_gt_index(const T &e) const { return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin(); } // Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`. int min_geq_index(const T &e) const { return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin(); } // Return the compressed index of the maximum registered value less than `e`. if not exists, return -1. int max_lt_index(const T &e) const { return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1; } // Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1. int max_leq_index(const T &e) const { return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1; } private: std::vector<T> _xs; static bool is_strictly_sorted(const std::vector<T> &v) { return std::adjacent_find(v.begin(), v.end(), std::greater_equal<T>()) == v.end(); } }; CoordinateCompressorBuilder() : _xs(std::vector<T>{}) {} explicit CoordinateCompressorBuilder(const std::vector<T> &xs) : _xs(xs) {} explicit CoordinateCompressorBuilder(std::vector<T> &&xs) : _xs(std::move(xs)) {} template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr> CoordinateCompressorBuilder(const int n, Gen generator) { reserve(n); for (int i = 0; i < n; ++i) push(generator(i)); } // Attempt to preallocate enough memory for specified number of elements. void reserve(int n) { _xs.reserve(n); } // Add data. void push(const T &first) { _xs.push_back(first); } // Add data. void push(T &&first) { _xs.push_back(std::move(first)); } // Add data in the range of [first, last). template <typename Iterator> auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector<T>{}.push_back(*first), void()) { for (auto it = first; it != last; ++it) _xs.push_back(*it); } // Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`. template <typename Iterable> auto push(const Iterable &iterable) -> decltype(std::vector<T>{}.push_back(*iterable.begin()), void()) { push(iterable.begin(), iterable.end()); } // Add data. template <typename ...Args> void emplace(Args &&...args) { _xs.emplace_back(std::forward<Args>(args)...); } // Build compressor. auto build() { std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end()); return Compressor {_xs}; } // Build compressor from vector. static auto build(const std::vector<T> &xs) { return CoordinateCompressorBuilder(xs).build(); } // Build compressor from vector. static auto build(std::vector<T> &&xs) { return CoordinateCompressorBuilder(std::move(xs)).build(); } // Build compressor from generator. template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr> static auto build(const int n, Gen generator) { return CoordinateCompressorBuilder<T>(n, generator).build(); } private: std::vector<T> _xs; }; } // namespace suisen #line 8 "test/src/graph/functional_graph/abc254_g.test.cpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, q; std::cin >> n >> m >> q; std::vector<suisen::RangeSet<int, false>> range_sets(n); for (int i = 0; i < m; ++i) { int a, b, c; std::cin >> a >> b >> c; --a, --b, --c; range_sets[a].insert(b, c); } suisen::CoordinateCompressorBuilder<int> comp_builder; std::vector<std::tuple<int, int, int, int>> queries(q); for (auto& [x, y, z, w] : queries) { std::cin >> x >> y >> z >> w; --x, --y, --z, --w; if (y > w) std::swap(x, z), std::swap(y, w); comp_builder.push(y); } std::vector<std::pair<int, int>> ranges; for (const auto& st : range_sets) for (const auto& [l, r] : st) { ranges.emplace_back(l, r); comp_builder.push(r); } std::sort(ranges.begin(), ranges.end()); const int range_num = ranges.size(); const auto comp = comp_builder.build(); const int k = comp.size(); suisen::FunctionalGraph g(k); { int i = 0, max_r = -1; for (int j = 0; j < k; ++j) { const int pos = comp.decomp(j); while (i < range_num and ranges[i].first <= pos) max_r = std::max(max_r, ranges[i++].second); g[j] = max_r < pos ? j : comp[max_r]; } } const auto doubling = g.doubling(range_num); for (auto& [x, y, z, w] : queries) { const int ans = w - y; if (const auto itx = range_sets[x].find_range(y); itx != range_sets[x].end()) y = itx->second; if (const auto itz = range_sets[z].find_range(w); itz != range_sets[z].end()) w = itz->first; if (y >= w) { std::cout << ans + (x != z) << '\n'; } else { const int w_ = w; const auto opt_res = doubling.step_until(comp[y], [&](int v) { return comp.decomp(v) >= w_; }); std::cout << (opt_res.has_value() ? ans + opt_res->step + 1 : -1) << '\n'; } } return 0; }