This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/util/container_utils.hpp"
#ifndef SUISEN_CONTAINER_UTILS #define SUISEN_CONTAINER_UTILS #include <vector> #include <optional> #include <sstream> #include "library/io/input_stream.hpp" #include "library/io/output_stream.hpp" #include "library/type_traits/type_traits.hpp" namespace suisen { template <typename T> int count_leq(const std::vector<T> &v, const T &key) { return std::upper_bound(v.begin(), v.end(), key) - v.begin(); } template <typename T> int count_lt(const std::vector<T> &v, const T &key) { return std::lower_bound(v.begin(), v.end(), key) - v.begin(); } template <typename T> int count_geq(const std::vector<T> &v, const T &key) { return v.size() - count_lt(v, key); } template <typename T> int count_gt(const std::vector<T> &v, const T &key) { return v.size() - count_leq(v, key); } template <typename Container, typename Key> auto min_geq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) { if (auto it = container.lower_bound(key); it == container.end()) return std::nullopt; else return std::make_optional(*it); } template <typename Container, typename Key> auto min_gt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) { if (auto it = container.upper_bound(key); it == container.end()) return std::nullopt; else return std::make_optional(*it); } template <typename Container, typename Key> auto max_leq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) { if (auto it = container.upper_bound(key); it == container.begin()) return std::nullopt; else return std::make_optional(*--it); } template <typename Container, typename Key> auto max_lt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) { if (auto it = container.lower_bound(key); it == container.begin()) return std::nullopt; else return std::make_optional(*--it); } template <typename T> std::optional<T> min_geq(const std::vector<T> &v, const T &key) { auto it = std::lower_bound(v.begin(), v.end(), key); return it == v.end() ? std::nullopt : std::make_optional(*it); } template <typename T> std::optional<T> min_gt(const std::vector<T> &v, const T &key) { auto it = std::upper_bound(v.begin(), v.end(), key); return it == v.end() ? std::nullopt : std::make_optional(*it); } template <typename T> std::optional<T> max_leq(const std::vector<T> &v, const T &key) { auto it = std::upper_bound(v.begin(), v.end(), key); return it == v.begin() ? std::nullopt : std::make_optional(*--it); } template <typename T> std::optional<T> max_lt(const std::vector<T> &v, const T &key) { auto it = std::lower_bound(v.begin(), v.end(), key); return it == v.begin() ? std::nullopt : std::make_optional(*--it); } __int128_t stoi128(const std::string& s) { __int128_t res; io::InputStream{std::istringstream{s}} >> res; return res; } __uint128_t stou128(const std::string& s) { __uint128_t res; io::InputStream{std::istringstream{s}} >> res; return res; } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> std::string join(const Iterable& v, const std::string& sep, const std::string& end) { io::OutputStream os{ std::ostringstream{} }; os.print_all(v, sep, end); return os.get_stream().str(); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> std::vector<Iterable> split(const Iterable &s, const typename Iterable::value_type &delim) { std::vector<Iterable> res; for (auto itl = s.begin(), itr = itl;; itl = ++itr) { while (itr != s.end() and *itr != delim) ++itr; res.emplace_back(itl, itr); if (itr == s.end()) return res; } } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void concat(Iterable& s, const Iterable& t) { s.reserve(std::size(s) + std::size(t)); std::copy(std::begin(t), std::end(t), std::back_inserter(s)); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> Iterable concatenated(Iterable s, const Iterable& t) { concat(s, t); return s; } template <typename Func, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> auto mapped_vec(const Func& f, const Iterable& s) { std::vector<std::invoke_result_t<Func, typename Iterable::value_type>> v; v.reserve(std::size(s)), std::transform(s.begin(), s.end(), std::back_inserter(v), f); return v; } template <typename T, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> auto copied_vec(const Iterable& s) { std::vector<T> v; v.reserve(std::size(s)), std::copy(s.begin(), s.end(), std::back_inserter(v)); return v; } namespace charmap { int fd(char c) { return c - '0'; } int fa(char c) { return c - 'a'; } int fA(char c) { return c - 'A'; } int faA(char c) { return c <= 'Z' ? c - 'A' : 26 + (c - 'a'); } } // val = Sum_i res[i] * base^i template <int base = 2, typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::string digits_str(T val, size_t width = 0) { static_assert(2 <= base and base <= 10); std::string res; for (; val or res.size() < width; val /= base) res += '0' + (val % base); return res; } // val = Sum_i res[i] * base^i template <typename T, typename U = int, std::enable_if_t<std::conjunction_v<std::is_integral<T>, std::is_integral<U>>, std::nullptr_t> = nullptr> std::vector<U> digits(T val, U base = 10) { std::vector<U> res; for (; val; val /= base) res.push_back(val % base); if (res.empty()) res.push_back(T{ 0 }); return res; } } // namespace suisen #endif // SUISEN_CONTAINER_UTILS
#line 1 "library/util/container_utils.hpp" #include <vector> #include <optional> #include <sstream> #line 1 "library/io/input_stream.hpp" #include <iostream> #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 6 "library/io/input_stream.hpp" namespace suisen::io { template <typename IStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::istream, std::remove_reference_t<IStream>>, std::negation<std::is_const<std::remove_reference_t<IStream>>>>, std::nullptr_t> = nullptr> struct InputStream { private: using istream_type = std::remove_reference_t<IStream>; IStream is; struct { InputStream* is; template <typename T> operator T() { T e; *is >> e; return e; } } _reader{ this }; public: template <typename IStream_> InputStream(IStream_ &&is) : is(std::move(is)) {} template <typename IStream_> InputStream(IStream_ &is) : is(is) {} template <typename T> InputStream& operator>>(T& e) { if constexpr (suisen::is_readable_v<T>) is >> e; else _read(e); return *this; } auto read() { return _reader; } template <typename Head, typename... Tail> void read(Head& head, Tail &...tails) { ((*this >> head) >> ... >> tails); } istream_type& get_stream() { return is; } private: static __uint128_t _stou128(const std::string& s) { __uint128_t ret = 0; for (char c : s) if ('0' <= c and c <= '9') ret = 10 * ret + c - '0'; return ret; } static __int128_t _stoi128(const std::string& s) { return (s[0] == '-' ? -1 : +1) * _stou128(s); } void _read(__uint128_t& v) { v = _stou128(std::string(_reader)); } void _read(__int128_t& v) { v = _stoi128(std::string(_reader)); } template <typename T, typename U> void _read(std::pair<T, U>& a) { *this >> a.first >> a.second; } template <size_t N = 0, typename ...Args> void _read(std::tuple<Args...>& a) { if constexpr (N < sizeof...(Args)) *this >> std::get<N>(a), _read<N + 1>(a); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void _read(Iterable& a) { for (auto& e : a) *this >> e; } }; template <typename IStream> InputStream(IStream &&) -> InputStream<IStream>; template <typename IStream> InputStream(IStream &) -> InputStream<IStream&>; InputStream cin{ std::cin }; auto read() { return cin.read(); } template <typename Head, typename... Tail> void read(Head& head, Tail &...tails) { cin.read(head, tails...); } } // namespace suisen::io namespace suisen { using io::read; } // namespace suisen #line 1 "library/io/output_stream.hpp" #line 6 "library/io/output_stream.hpp" namespace suisen::io { template <typename OStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::ostream, std::remove_reference_t<OStream>>, std::negation<std::is_const<std::remove_reference_t<OStream>>>>, std::nullptr_t> = nullptr> struct OutputStream { private: using ostream_type = std::remove_reference_t<OStream>; OStream os; public: template <typename OStream_> OutputStream(OStream_ &&os) : os(std::move(os)) {} template <typename OStream_> OutputStream(OStream_ &os) : os(os) {} template <typename T> OutputStream& operator<<(const T& e) { if constexpr (suisen::is_writable_v<T>) os << e; else _print(e); return *this; } void print() { *this << '\n'; } template <typename Head, typename... Tail> void print(const Head& head, const Tail &...tails) { *this << head, ((*this << ' ' << tails), ...), *this << '\n'; } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") { for (auto it = v.begin(); it != v.end();) if (*this << *it; ++it != v.end()) *this << sep; *this << end; } ostream_type& get_stream() { return os; } private: void _print(__uint128_t value) { char buffer[41], *d = std::end(buffer); do *--d = '0' + (value % 10), value /= 10; while (value); os.rdbuf()->sputn(d, std::end(buffer) - d); } void _print(__int128_t value) { if (value < 0) *this << '-'; _print(__uint128_t(value < 0 ? -value : value)); } template <typename T, typename U> void _print(const std::pair<T, U>& a) { *this << a.first << ' ' << a.second; } template <size_t N = 0, typename ...Args> void _print(const std::tuple<Args...>& a) { if constexpr (N < std::tuple_size_v<std::tuple<Args...>>) { if constexpr (N) *this << ' '; *this << std::get<N>(a), _print<N + 1>(a); } } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void _print(const Iterable& a) { print_all(a, " ", ""); } }; template <typename OStream_> OutputStream(OStream_ &&) -> OutputStream<OStream_>; template <typename OStream_> OutputStream(OStream_ &) -> OutputStream<OStream_&>; OutputStream cout{ std::cout }, cerr{ std::cerr }; template <typename... Args> void print(const Args &... args) { cout.print(args...); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void print_all(const Iterable& v, const std::string& sep = " ", const std::string& end = "\n") { cout.print_all(v, sep, end); } } // namespace suisen::io namespace suisen { using io::print, io::print_all; } // namespace suisen #line 11 "library/util/container_utils.hpp" namespace suisen { template <typename T> int count_leq(const std::vector<T> &v, const T &key) { return std::upper_bound(v.begin(), v.end(), key) - v.begin(); } template <typename T> int count_lt(const std::vector<T> &v, const T &key) { return std::lower_bound(v.begin(), v.end(), key) - v.begin(); } template <typename T> int count_geq(const std::vector<T> &v, const T &key) { return v.size() - count_lt(v, key); } template <typename T> int count_gt(const std::vector<T> &v, const T &key) { return v.size() - count_leq(v, key); } template <typename Container, typename Key> auto min_geq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) { if (auto it = container.lower_bound(key); it == container.end()) return std::nullopt; else return std::make_optional(*it); } template <typename Container, typename Key> auto min_gt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) { if (auto it = container.upper_bound(key); it == container.end()) return std::nullopt; else return std::make_optional(*it); } template <typename Container, typename Key> auto max_leq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) { if (auto it = container.upper_bound(key); it == container.begin()) return std::nullopt; else return std::make_optional(*--it); } template <typename Container, typename Key> auto max_lt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) { if (auto it = container.lower_bound(key); it == container.begin()) return std::nullopt; else return std::make_optional(*--it); } template <typename T> std::optional<T> min_geq(const std::vector<T> &v, const T &key) { auto it = std::lower_bound(v.begin(), v.end(), key); return it == v.end() ? std::nullopt : std::make_optional(*it); } template <typename T> std::optional<T> min_gt(const std::vector<T> &v, const T &key) { auto it = std::upper_bound(v.begin(), v.end(), key); return it == v.end() ? std::nullopt : std::make_optional(*it); } template <typename T> std::optional<T> max_leq(const std::vector<T> &v, const T &key) { auto it = std::upper_bound(v.begin(), v.end(), key); return it == v.begin() ? std::nullopt : std::make_optional(*--it); } template <typename T> std::optional<T> max_lt(const std::vector<T> &v, const T &key) { auto it = std::lower_bound(v.begin(), v.end(), key); return it == v.begin() ? std::nullopt : std::make_optional(*--it); } __int128_t stoi128(const std::string& s) { __int128_t res; io::InputStream{std::istringstream{s}} >> res; return res; } __uint128_t stou128(const std::string& s) { __uint128_t res; io::InputStream{std::istringstream{s}} >> res; return res; } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> std::string join(const Iterable& v, const std::string& sep, const std::string& end) { io::OutputStream os{ std::ostringstream{} }; os.print_all(v, sep, end); return os.get_stream().str(); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> std::vector<Iterable> split(const Iterable &s, const typename Iterable::value_type &delim) { std::vector<Iterable> res; for (auto itl = s.begin(), itr = itl;; itl = ++itr) { while (itr != s.end() and *itr != delim) ++itr; res.emplace_back(itl, itr); if (itr == s.end()) return res; } } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> void concat(Iterable& s, const Iterable& t) { s.reserve(std::size(s) + std::size(t)); std::copy(std::begin(t), std::end(t), std::back_inserter(s)); } template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> Iterable concatenated(Iterable s, const Iterable& t) { concat(s, t); return s; } template <typename Func, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> auto mapped_vec(const Func& f, const Iterable& s) { std::vector<std::invoke_result_t<Func, typename Iterable::value_type>> v; v.reserve(std::size(s)), std::transform(s.begin(), s.end(), std::back_inserter(v), f); return v; } template <typename T, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr> auto copied_vec(const Iterable& s) { std::vector<T> v; v.reserve(std::size(s)), std::copy(s.begin(), s.end(), std::back_inserter(v)); return v; } namespace charmap { int fd(char c) { return c - '0'; } int fa(char c) { return c - 'a'; } int fA(char c) { return c - 'A'; } int faA(char c) { return c <= 'Z' ? c - 'A' : 26 + (c - 'a'); } } // val = Sum_i res[i] * base^i template <int base = 2, typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::string digits_str(T val, size_t width = 0) { static_assert(2 <= base and base <= 10); std::string res; for (; val or res.size() < width; val /= base) res += '0' + (val % base); return res; } // val = Sum_i res[i] * base^i template <typename T, typename U = int, std::enable_if_t<std::conjunction_v<std::is_integral<T>, std::is_integral<U>>, std::nullptr_t> = nullptr> std::vector<U> digits(T val, U base = 10) { std::vector<U> res; for (; val; val /= base) res.push_back(val % base); if (res.empty()) res.push_back(T{ 0 }); return res; } } // namespace suisen