#879683 (C++17) No.738 平らな農地

提出ソース
結果

問題	No.738 平らな農地
ユーザー	🦠みどりむし
提出日時	2023-06-10 15:13:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	340 ms / 2,000 ms
コード長	46,407 bytes
コンパイル時間	2,844 ms
コンパイル使用メモリ	241,772 KB
実行使用メモリ	34,696 KB
最終ジャッジ日時	2023-08-30 22:28:21
合計ジャッジ時間	19,144 ms
ジャッジサーバーID （参考情報）	judge13 / judge12
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	7 ms 4,384 KB
testcase_06	AC	8 ms 4,568 KB
testcase_07	AC	7 ms 4,376 KB
testcase_08	AC	4 ms 4,380 KB
testcase_09	AC	3 ms 4,376 KB
testcase_10	AC	2 ms 4,384 KB
testcase_11	AC	4 ms 4,376 KB
testcase_12	AC	3 ms 4,380 KB
testcase_13	AC	7 ms 4,380 KB
testcase_14	AC	3 ms 4,380 KB
testcase_15	AC	185 ms 30,212 KB
testcase_16	AC	187 ms 30,836 KB
testcase_17	AC	217 ms 30,508 KB
testcase_18	AC	210 ms 29,952 KB
testcase_19	AC	261 ms 32,140 KB
testcase_20	AC	191 ms 30,824 KB
testcase_21	AC	244 ms 32,200 KB
testcase_22	AC	198 ms 30,840 KB
testcase_23	AC	234 ms 31,380 KB
testcase_24	AC	237 ms 30,924 KB
testcase_25	AC	3 ms 4,376 KB
testcase_26	AC	3 ms 4,380 KB
testcase_27	AC	4 ms 4,380 KB
testcase_28	AC	3 ms 4,380 KB
testcase_29	AC	3 ms 4,384 KB
testcase_30	AC	3 ms 4,384 KB
testcase_31	AC	3 ms 4,380 KB
testcase_32	AC	3 ms 4,376 KB
testcase_33	AC	3 ms 4,380 KB
testcase_34	AC	3 ms 4,380 KB
testcase_35	AC	3 ms 4,380 KB
testcase_36	AC	3 ms 4,380 KB
testcase_37	AC	3 ms 4,380 KB
testcase_38	AC	3 ms 4,380 KB
testcase_39	AC	3 ms 4,384 KB
testcase_40	AC	3 ms 4,376 KB
testcase_41	AC	3 ms 4,376 KB
testcase_42	AC	3 ms 4,376 KB
testcase_43	AC	3 ms 4,380 KB
testcase_44	AC	3 ms 4,380 KB
testcase_45	AC	180 ms 32,880 KB
testcase_46	AC	181 ms 30,404 KB
testcase_47	AC	178 ms 32,200 KB
testcase_48	AC	159 ms 31,048 KB
testcase_49	AC	156 ms 30,808 KB
testcase_50	AC	162 ms 32,016 KB
testcase_51	AC	189 ms 32,212 KB
testcase_52	AC	173 ms 31,144 KB
testcase_53	AC	178 ms 31,532 KB
testcase_54	AC	187 ms 32,356 KB
testcase_55	AC	194 ms 32,512 KB
testcase_56	AC	187 ms 31,880 KB
testcase_57	AC	173 ms 30,084 KB
testcase_58	AC	177 ms 31,584 KB
testcase_59	AC	173 ms 32,836 KB
testcase_60	AC	167 ms 32,756 KB
testcase_61	AC	171 ms 32,480 KB
testcase_62	AC	168 ms 30,404 KB
testcase_63	AC	195 ms 32,992 KB
testcase_64	AC	183 ms 32,624 KB
testcase_65	AC	269 ms 30,848 KB
testcase_66	AC	283 ms 31,800 KB
testcase_67	AC	221 ms 32,396 KB
testcase_68	AC	214 ms 33,308 KB
testcase_69	AC	313 ms 33,592 KB
testcase_70	AC	258 ms 34,544 KB
testcase_71	AC	28 ms 8,392 KB
testcase_72	AC	178 ms 28,544 KB
testcase_73	AC	160 ms 26,816 KB
testcase_74	AC	220 ms 29,736 KB
testcase_75	AC	283 ms 32,332 KB
testcase_76	AC	231 ms 33,176 KB
testcase_77	AC	309 ms 32,408 KB
testcase_78	AC	340 ms 34,448 KB
testcase_79	AC	325 ms 34,696 KB
testcase_80	AC	250 ms 33,512 KB
testcase_81	AC	285 ms 32,600 KB
testcase_82	AC	298 ms 33,784 KB
testcase_83	AC	204 ms 30,984 KB
testcase_84	AC	173 ms 29,996 KB
testcase_85	AC	324 ms 34,524 KB
testcase_86	AC	294 ms 32,184 KB
testcase_87	AC	96 ms 33,436 KB
testcase_88	AC	91 ms 32,204 KB
testcase_89	AC	1 ms 4,376 KB
testcase_90	AC	1 ms 4,376 KB
testcase_91	AC	1 ms 4,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #include <bits/stdc++.h>
// #include "template.hpp"
#include <iostream>
/* #expanded [utility/functional.hpp] */
#include <functional>
#include <utility>
namespace lib {namespace internal {template<class T> constexpr T plus(const T a, const T b) { return std::plus<T>{}(a, b); }template<class T> constexpr T minus(const T a, const T b) { return std::minus<T>{}(a, b); }template<class T> constexpr T bitxor(const T a, const T b) { return a xor b; }}template<class T1, class T2> inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return (a<b ? a=b, true : false); }template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return (a>b ? a=b, true : false); }template<class T> inline constexpr T sign(const T x) {return (x > 0) - (x < 0);}template<class T, T FROM_MIN, T FROM_MAX, T TO_MIN, T TO_MAX> inline constexpr T mapping(const T x) {return (x - FROM_MIN) * (TO_MAX - TO_MIN) / (FROM_MAX - FROM_MIN) + TO_MIN;}template<class T> inline constexpr T mapping(const T x, const T from_min, const T from_max, const T to_min, const T to_max) {return (x - from_min) * (to_max - to_min) / (from_max - from_min) + to_min;}}
/* [utility/functional.hpp] */
/* #expanded [snippet/iterations.hpp] */
#include <type_traits>
/* #expanded [snippet/internal/overload.hpp] */
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
/* [snippet/internal/overload.hpp] */
#define LOOP(n) REPI($_, (n))
#define REPI(i,n) for(int i=0, i##_length=static_cast<int>(n); i<i##_length; ++i)
#define REPF(i,l,r) for(std::common_type_t<decltype(l),decltype(r)> i=(l), i##_last=(r); i<i##_last; ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<decltype(l),decltype(r),decltype(s)> i=(l), i##_last=(r); i<i##_last; i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<decltype(l),decltype(r)> i=(r), i##_last=(l); --i>=i##_last;)
#define REPRS(i,l,r,s) for(std::common_type_t<decltype(l),decltype(r),decltype(s)> i=(l)+((r)-(l)-1)/(s)*(s), i##_last=(l); i>=i##_last; (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, i##_last=static_cast<int>(n); i<=i##_last; ++i)
#define FORI(i,l,r) for(std::common_type_t<decltype(l),decltype(r)> i=(l), i##_last=(r); i<=i##_last; ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<decltype(l),decltype(r),decltype(s)> i=(l), i##_last=(r); i<=i##_last; i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<decltype(l),decltype(r)> i=(r), i##_last=(l); i>=i##_last; --i)
#define FORRS(i,l,r,s) for(std::common_type_t<decltype(l),decltype(r),decltype(s)> i=(l)+((r)-(l))/(s)*(s), i##_last=(l); i>=i##_last; i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [snippet/iterations.hpp] */
/* #expanded [data_structure/wavelet_matrix.hpp] */
#include <cassert>
#include <cstdint>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <array>
#include <iterator>
#include <optional>
#include <limits>
/* #expanded [internal/dev_env.hpp] */
#ifdef LOCAL_JUDGE
constexpr bool DEV_ENV = true;constexpr bool NO_EXCEPT = false;
#else
constexpr bool DEV_ENV = false;constexpr bool NO_EXCEPT = true;
#endif
/* [internal/dev_env.hpp] */
/* #expanded [internal/types.hpp] */
namespace lib {namespace internal {using size_t = std::int32_t;using int128_t = __int128_t;using uint128_t = __uint128_t;}}
/* [internal/types.hpp] */
/* #expanded [internal/iterator.hpp] */
namespace lib {namespace internal {template<class T>struct iterator_interface {using iterator_category = std::output_iterator_tag;using difference_type = size_t;using value_type = T;using pointer = T*;using reference = T&;};template<class T>struct forward_iterator : iterator_interface<T> {using iterator_category = std::forward_iterator_tag;};template<class T>struct bidirectional_iterator_interface : forward_iterator<T> {using iterator_category = std::bidirectional_iterator_tag;};template<class T>struct random_access_iterator_base : bidirectional_iterator_interface<T> {using iterator_category = std::random_access_iterator_tag;using difference_type = typename bidirectional_iterator_interface<T>::difference_type;public:};template<class T, class container>struct container_iterator_interface : public random_access_iterator_base<T> {using difference_type = typename bidirectional_iterator_interface<T>::difference_type;protected:const container *const _ref;difference_type _pos;container_iterator_interface(const container *const ref, const difference_type& pos) noexcept(NO_EXCEPT) : _ref(ref), _pos(pos) {}public:inline const container* ref() const noexcept(NO_EXCEPT) { return this->_ref; }inline difference_type pos() const noexcept(NO_EXCEPT) { return this->_pos; }inline difference_type& pos() { return this->_pos; }inline container_iterator_interface& operator++() noexcept(NO_EXCEPT) { return ++this->pos(), *this; }inline container_iterator_interface& operator--() noexcept(NO_EXCEPT) { return --this->pos(), *this; }inline container_iterator_interface& operator+=(const difference_type count) noexcept(NO_EXCEPT) { return this->pos() += count, *this; }inline container_iterator_interface& operator-=(const difference_type count) noexcept(NO_EXCEPT) { return this->pos() -= count, *this; }inline difference_type operator-(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return this->pos() - other.pos(); }inline bool operator<(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return *this - other < 0; }inline bool operator>(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return *this - other > 0; }inline bool operator<=(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return not (*this > other); }inline bool operator>=(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return not (*this < other); }inline bool operator!=(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return this->ref() != other.ref() or *this < other or *this > other; }inline bool operator==(const container_iterator_interface& other) const noexcept(NO_EXCEPT) { return not (*this != other); }};template<class I, std::enable_if_t<std::is_base_of_v<random_access_iterator_base<typename I::value_type>,I>>* = nullptr>inline I operator+(I itr, const typename I::difference_type count) noexcept(NO_EXCEPT) { return itr += count, itr; }template<class I, std::enable_if_t<std::is_base_of_v<random_access_iterator_base<typename I::value_type>,I>>* = nullptr>inline I operator-(I itr, const typename I::difference_type count) noexcept(NO_EXCEPT) { return itr -= count, itr; }}}
/* [internal/iterator.hpp] */
/* #expanded [internal/range_reference.hpp] */
/* #expanded [constants.hpp] */
/* #expanded [snippet/aliases.hpp] */
/* #expanded [snippet/internal/types.hpp] */
namespace lib {using i16 = std::int16_t;using u16 = std::uint16_t;using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t;using u128 = __uint128_t;
#endif
using uint = unsigned;using ll = long long;using ull = unsigned long long;using ld = long double;}
/* [snippet/internal/types.hpp] */
#define until(...) while(!(__VA_ARGS__))
#define ALL(x) std::begin((x)),std::end((x))
#define RALL(x) std::rbegin((x)),std::rend((x))
#define $F first
#define $S second
namespace lib {template<class T> using spair = std::pair<T,T>;}namespace std {using bit_reference = std::vector<bool>::reference;bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; }bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; }}
/* [snippet/aliases.hpp] */
namespace lib {i32 INF32 = (std::numeric_limits<i32>::max() >> 1) - 1;i64 INF64 = (std::numeric_limits<i64>::max() >> 1) - 1;constexpr char LN = '\n';constexpr char SPC = ' ';constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };enum class comp : std::uint8_t {equal_to,not_equal_to,equals = equal_to,eq = equal_to,under,over,or_under,or_over,less = under,more = over,less_than = under,more_than = over,not_less_than = or_over,not_more_than = or_under,leq = or_under,geq = or_over};enum class interval : std::uint8_t {right_open,left_open,open,closed,};}
/* [constants.hpp] */
namespace lib {namespace internal {template<class Super> struct range_reference {using size_type = typename Super::size_type;using iterator = typename Super::iterator;protected:Super *const _super;const size_type _begin, _end;range_reference(Super *const super, const size_type begin, const size_type end) noexcept(NO_EXCEPT) : _super(super), _begin(begin), _end(end) {}public:inline iterator begin() const noexcept(NO_EXCEPT) { return std::next(_super->begin(), this->_begin); }inline iterator end() const noexcept(NO_EXCEPT) { return std::next(_super->begin(), this->_end); }inline size_type size() const noexcept(NO_EXCEPT) { return this->_end - this->_begin; }protected:inline range_reference sub_range(size_type l, size_type r) const noexcept(NO_EXCEPT) {l = _super->_positivize_index(l), r = _super->_positivize_index(r);assert(0 <= l and l <= r and r <= this->size());return range_reference(_super, this->_begin + l, this->_begin + r);}public:template<lib::interval rng = lib::interval::right_open>inline range_reference range(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {if constexpr(rng == lib::interval::right_open) return this->sub_range(l, r);if constexpr(rng == lib::interval::left_open) return this->sub_range(l+1, r+1);if constexpr(rng == lib::interval::open) return this->sub_range(l+1, r);if constexpr(rng == lib::interval::closed) return this->sub_range(l, r+1);}inline range_reference range() const noexcept(NO_EXCEPT) { return range_reference(this->_begin, this->_end); }inline range_reference operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) { return this->sub_range(l, r); }inline range_reference subseq(const size_type p, const size_type c) const noexcept(NO_EXCEPT) { return this->sub_range(p, p+c); }inline range_reference subseq(const size_type p) const noexcept(NO_EXCEPT) { return this->sub_range(p, this->size()); }};}}
/* [internal/range_reference.hpp] */
/* #expanded [iterable/compression.hpp] */
#include <map>
namespace lib {template<class T = i64, class container = std::vector<internal::size_t>>struct compression : container {using size_type = internal::size_t;protected:std::vector<T> values;public:explicit compression() noexcept(NO_EXCEPT) {}template<class I> compression(const I first, const I last) noexcept(NO_EXCEPT) {this->values.assign(first, last);std::sort(this->values.begin(), this->values.end());this->values.erase(std::unique(this->values.begin(), this->values.end()), this->values.end());this->resize(std::distance(first, last));auto itr = std::begin(*this);auto e = first;for(; e!=last; ++itr, ++e) {*itr = this->rank(*e);}}inline size_type rank(const T& val) const noexcept(NO_EXCEPT) {return static_cast<size_type>(std::distance(this->values.begin(), std::lower_bound(this->values.begin(), this->values.end(), val)));}inline size_type rank2(const T& val) const noexcept(NO_EXCEPT) {return static_cast<size_type>(std::distance(this->values.begin(), std::upper_bound(this->values.begin(), this->values.end(), val))) - 1;}inline T value(const size_type rank) const noexcept(NO_EXCEPT) { return this->values[rank]; }inline T operator()(const internal::size_t val) const noexcept(NO_EXCEPT) { return this->values[val]; }};}
/* [iterable/compression.hpp] */
/* #expanded [numeric/bit.hpp] */
namespace lib {
#define LIB_STATUC_ASSERT_UNSIGNED(T) static_assert(std::is_unsigned_v<T>, "only unsigned type is supported")
template<class T>__attribute__((target("bmi,bmi2,popcnt"))) inline constexpr int popcount(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);using u = unsigned int;using ul = unsigned long;using ull = unsigned long long;if constexpr(std::is_same_v<T,u>) return __builtin_popcount(v);else if constexpr(std::is_same_v<T,ul>) return __builtin_popcountl(v);else if constexpr(std::is_same_v<T,ull>) return __builtin_popcountll(v);else return __builtin_popcountll(static_cast<ull>(v));}template<class T>__attribute__((target("bmi,bmi2,lzcnt"))) inline constexpr int countl_zero(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);using u = unsigned int;using ul = unsigned long;using ull = unsigned long long;constexpr int DIGITS = std::numeric_limits<T>::digits;if(v == 0) return DIGITS;constexpr int DIGITS_U = std::numeric_limits<u>::digits;constexpr int DIGITS_UL = std::numeric_limits<ul>::digits;constexpr int DIGITS_ULL = std::numeric_limits<ull>::digits;if constexpr(DIGITS <= DIGITS_U) return __builtin_clz(v) - DIGITS_U + DIGITS;if constexpr(DIGITS <= DIGITS_UL) return __builtin_clzl(v) - DIGITS_UL + DIGITS;if constexpr(DIGITS <= DIGITS_ULL) return __builtin_clzll(v) - DIGITS_ULL + DIGITS;else {static_assert(DIGITS <= DIGITS_ULL << 1);constexpr ull MAX_ULL = std::numeric_limits<ull>::max();const ull high = v >> DIGITS_ULL;const ull low = v & MAX_ULL;if(high > 0) return __builtin_clzll(high) - (DIGITS_ULL << 1) + DIGITS;return __builtin_clzll(low) - DIGITS_ULL + DIGITS;}}template<class T>inline constexpr int bit_width(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);return std::numeric_limits<T>::digits - countl_zero(v);}template<class T>inline constexpr int highest_bit_pos(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);return bit_width(v) - 1;}template<class T>__attribute__((target("bmi,bmi2,lzcnt")))inline constexpr int lowest_bit_pos(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);using u = unsigned int;using ul = unsigned long;using ull = unsigned long long;constexpr int DIGITS = std::numeric_limits<T>::digits;constexpr int DIGITS_U = std::numeric_limits<u>::digits;constexpr int DIGITS_UL = std::numeric_limits<ul>::digits;constexpr int DIGITS_ULL = std::numeric_limits<ull>::digits;if constexpr(DIGITS <= DIGITS_U) return __builtin_ffs(v) - 1;if constexpr(DIGITS <= DIGITS_UL) return __builtin_ffsl(v) - 1;if constexpr(DIGITS <= DIGITS_ULL) return __builtin_ffsll(v) - 1;else {static_assert(DIGITS <= DIGITS_ULL << 1);constexpr ull MAX_ULL = std::numeric_limits<ull>::max();const ull high = v >> DIGITS_ULL;const ull low = v & MAX_ULL;if(low > 0) return __builtin_ffsll(low) - 1;return __builtin_ffsll(high) + DIGITS_ULL - 1;}}template<class T>inline constexpr int countr_zero(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);if(v == 0) return std::numeric_limits<T>::digits;return lowest_bit_pos(v);}template<class T>inline constexpr T bit_ceil(const T v) noexcept(NO_EXCEPT) {LIB_STATUC_ASSERT_UNSIGNED(T);if(v <= 1U) return 1;if constexpr(std::is_same_v<T,decltype(+v)>) return T{1} << bit_width<T>(v - 1);else {constexpr int d = std::numeric_limits<unsigned>::digits - std::numeric_limits<T>::digits;return T(1U << bit_width<T>(v - 1) + d) >> d;}}
#undef LIB_STATUC_ASSERT_UNSIGNED
}
/* [numeric/bit.hpp] */
/* #expanded [data_structure/bit_vector.hpp] */
#include <immintrin.h>
namespace lib {struct bit_vector {using size_type = internal::size_t;private:static constexpr size_type w = 64;std::vector<std::uint64_t> _block;std::vector<size_type> _count;size_type _n, _zeros;public:bit_vector(const size_type _n = 0) noexcept(NO_EXCEPT) { this->init(_n); }template<class I> explicit bit_vector(const I first, const I last) noexcept(NO_EXCEPT) : bit_vector(std::distance(first, last)) {size_type pos = 0;for(auto itr=first; itr != last; ++pos, ++itr) if(*itr) this->set(pos);}template<class T> bit_vector(const std::initializer_list<T>& init_list) noexcept(NO_EXCEPT) : bit_vector(std::begin(init_list), std::end(init_list)) {}inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }inline size_type zeros() const noexcept(NO_EXCEPT) { return this->_zeros; }inline size_type ones() const noexcept(NO_EXCEPT) { return this->_n - this->_zeros; }inline void set(const size_type k) noexcept(NO_EXCEPT) { this->_block[k / w] |= 1LL << (k % w); }inline bool get(const size_type k) const noexcept(NO_EXCEPT) { return std::uint32_t(this->_block[k / w] >> (k % w)) & 1U; }__attribute__((optimize("O3", "unroll-loops"))) void init(const int _n) noexcept(NO_EXCEPT) {this->_n = this->_zeros = _n;this->_block.resize(_n / w + 1, 0);this->_count.resize(this->_block.size(), 0);}__attribute__((target("popcnt"))) void build() noexcept(NO_EXCEPT) {for(auto k = 1UL; k < this->_block.size(); ++k) this->_count[k] = this->_count[k-1] + static_cast<size_type>(_mm_popcnt_u64(this->_block[k-1]));this->_zeros = this->rank0(this->_n);}__attribute__((target("bmi2,popcnt"))) inline size_type rank1(const size_type k) const noexcept(NO_EXCEPT) {return this->_count[k / w] + static_cast<size_type>(_mm_popcnt_u64(_bzhi_u64(this->_block[k / w], k % w)));}inline size_type rank0(size_type k) const noexcept(NO_EXCEPT) { return k - this->rank1(k); }inline size_type rank(const bool bit, const size_type k) const noexcept(NO_EXCEPT) {return bit ? this->rank1(k) : this->rank0(k);}__attribute__((target("bmi2,popcnt"))) inline size_type select(const bool bit, const size_type rank) const noexcept(NO_EXCEPT) {if (!bit and rank > this->zeros()) { return this->_n + 1; }if (bit and rank > this->ones()) { return this->_n + 1; }size_type block_pos = 0;{size_type ng = -1, ok = static_cast<size_type>(this->_count.size());while(ok - ng > 1) {size_type mid = (ng + ok) / 2;size_type cnt = this->_count[mid];if(!bit) cnt = mid * w - cnt;(cnt >= rank ? ok : ng) = mid;}block_pos = ok;}const size_type base_index = (block_pos - 1) * w;const size_type count = this->_count[block_pos - 1];const std::uint64_t block = this->_block[block_pos - 1];size_type ng = -1, ok = w;while(ok - ng > 1) {const size_type mid = (ok + ng) / 2;size_type r = count + static_cast<size_type>(_mm_popcnt_u64(_bzhi_u64(block, mid)));if(!bit) r = base_index + mid - r;(r >= rank ? ok : ng) = mid;}return base_index + ok;}inline size_type select0(const size_type k) const noexcept(NO_EXCEPT) { return this->select(0, k); }inline size_type select1(const size_type k) const noexcept(NO_EXCEPT) { return this->select(1, k); }struct iterator : virtual internal::container_iterator_interface<bool,bit_vector> {iterator(const bit_vector *const ref, const size_type pos) noexcept(NO_EXCEPT) : internal::container_iterator_interface<bool,bit_vector>(ref, pos) {}inline bool operator*() const noexcept(NO_EXCEPT) { return this->ref()->get(this->pos()); }};inline iterator begin() const noexcept(NO_EXCEPT) { return iterator(this, 0); }inline iterator end() const noexcept(NO_EXCEPT) { return iterator(this, this->size()); }};}
/* [data_structure/bit_vector.hpp] */
namespace lib {namespace internal {namespace wavelet_matrix_impl {template<class T, class dict_type> struct base {using size_type = internal::size_t;private:size_type _n, _bits;std::vector<bit_vector> _index;std::vector<std::vector<T>> _sum;dict_type _first_pos;T _max = 0;public:base() {}template<class I> base(const I first, const I last) noexcept(NO_EXCEPT) { this->build(first, last); }template<class U> base(const std::initializer_list<U>& init_list) noexcept(NO_EXCEPT) : base(ALL(init_list)) {}inline size_type size() const noexcept(NO_EXCEPT) { return this->_n; }inline size_type bits() const noexcept(NO_EXCEPT) { return this->_bits; }template<class I> __attribute__((optimize("O3"))) void build(const I first, const I last) noexcept(NO_EXCEPT) {this->_n = static_cast<size_type>(std::distance(first, last));this->_max = first == last ? -1 : *std::max_element(first, last);this->_bits = bit_width<std::make_unsigned_t<T>>(this->_max + 1);this->_index.assign(this->_bits, this->_n);std::vector<T> bit(first, last), nxt(this->_n);this->_sum.assign(this->_bits+1, std::vector<T>(this->_n+1));{size_type i = 0;for(auto itr=first; itr!=last; ++i, ++itr) {this->_sum[this->_bits][i+1] = this->_sum[this->_bits][i] + *itr;}}REPD(h, this->_bits) {std::vector<size_type> vals;for(size_type i = 0; i < this->_n; ++i) {if((bit[i] >> h) & 1) this->_index[h].set(i);}this->_index[h].build();std::array<typename std::vector<T>::iterator,2> itrs{ std::begin(nxt), std::next(std::begin(nxt), this->_index[h].zeros()) };for(size_type i=0; i<this->_n; ++i) *itrs[this->_index[h].get(i)]++ = bit[i];REP(i, this->_n) this->_sum[h][i+1] = this->_sum[h][i] + nxt[i];std::swap(bit, nxt);}REPD(i, this->_n) this->_first_pos[bit[i]] = i;}protected:inline T get(const size_type k) const noexcept(NO_EXCEPT) { return this->_sum[this->_bits][k+1] - this->_sum[this->_bits][k]; }size_type select(const T& v, const size_type rank) const noexcept(NO_EXCEPT) {if (v > this->_max) return this->_n;if (this->_first_pos.count(v) == 0) return this->_n;size_type pos = this->_first_pos.at(v) + rank + 1;REP(h, this->_bits) {const bool bit = (v >> h) & 1;if(bit) pos -= this->_index[h].zeros();pos = this->_index[h].select(bit, pos);}return pos - 1;}inline T kth_smallest(size_type l, size_type r, size_type k) const noexcept(NO_EXCEPT) {T val = 0;for(size_type h = this->_bits - 1; h >= 0; --h) {size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(k < r0 - l0) {l = l0, r = r0;}else {k -= r0 - l0;val |= T{1} << h;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;}}return val;}inline size_type kth_smallest_index(size_type l, size_type r, size_type k) const noexcept(NO_EXCEPT) {T val = 0;for(size_type h = this->_bits - 1; h >= 0; --h) {size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(k < r0 - l0) {l = l0, r = r0;}else {k -= r0 - l0;val |= T{1} << h;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;}}size_type left = 0;REPD(h, this->_bits) {const bool bit = (val >> h) & 1;left = this->_index[h].rank(bit, left);if(bit) left += this->_index[h].zeros();}return this->select(val, l + k - left);}inline T kth_largest(const size_type l, const size_type r, const size_type k) const noexcept(NO_EXCEPT) {return this->kth_smallest(l, r, r-l-k-1);}inline size_type kth_largest_index(const size_type l, const size_type r, const size_type k) const noexcept(NO_EXCEPT) {return this->kth_smallest_index(l, r, r-l-k-1);}inline std::pair<size_type,size_type> succ0(const size_type l, const size_type r, const size_type h) const noexcept(NO_EXCEPT) {return std::make_pair(this->_index[h].rank0(l), this->_index[h].rank0(r));}inline std::pair<size_type,size_type> succ1(const size_type l, const size_type r, const size_type h) const noexcept(NO_EXCEPT) {size_type l0 = this->_index[h].rank0(l);size_type r0 = this->_index[h].rank0(r);size_type vals = this->_index[h].zeros();return std::make_pair(l + vals - l0, r + vals - r0);}T sum_in_range(const size_type l, const size_type r, const T& x, const T& y, const T& cur, const size_type bit) const noexcept(NO_EXCEPT) {if(l == r) return 0;if(bit == -1) {if(x <= cur and cur < y) return cur * (r - l);return 0;}const T& nxt = (T{1} << bit) | cur;const T& ones = ((T{1} << bit) - 1) | nxt;if(ones < x or y <= cur) return 0;if(x <= cur and ones < y) return this->_sum[bit+1][r] - this->_sum[bit+1][l];const size_type l0 = this->_index[bit].rank0(l), r0 = this->_index[bit].rank0(r);const size_type l1 = l - l0, r1 = r - r0;return this->sum_in_range(l0, r0, x, y, cur, bit - 1) + this->sum_in_range(this->_index[bit].zeros()+l1, this->_index[bit].zeros()+r1, x, y, nxt, bit - 1);}inline T sum_in_range(const size_type l, const size_type r, const T& x, const T& y) const noexcept(NO_EXCEPT) {return this->sum_in_range(l, r, x, y, 0, this->_bits-1);}inline T sum_under(const size_type l, const size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->sum_in_range(l, r, 0, v);}inline T sum_over(const size_type l, const size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->sum_in_range(l, r, v+1, std::numeric_limits<T>::max());}inline T sum_or_under(const size_type l, const size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->sum_in_range(l, r, 0, v+1);}inline T sum_or_over(const size_type l, const size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->sum_in_range(l, r, v, std::numeric_limits<T>::max());}inline T sum(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {return this->_sum[this->_bits][r] - this->_sum[this->_bits][l];}inline size_type count_under(size_type l, size_type r, const T& y) const noexcept(NO_EXCEPT) {if(y >= (T{1} << this->_bits)) return r - l;size_type res = 0;REPD(h, this->_bits) {bool f = (y >> h) & 1;size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(f) {res += r0 - l0;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;} else {l = l0;r = r0;}}return res;}inline size_type count_in_range(const size_type l, const size_type r, const T& x, const T& y) const noexcept(NO_EXCEPT) {return this->count_under(l, r, y) - this->count_under(l, r, x);}inline size_type count_or_under(size_type l, size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->count_under(l, r, v+1);}inline size_type count_over(size_type l, size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->count_or_over(l, r, v+1);}inline size_type count_or_over(size_type l, size_type r, const T& v) const noexcept(NO_EXCEPT) {return r - l - this->count_under(l, r, v);}inline size_type count_equal_to(const size_type l, const size_type r, const T& v) const noexcept(NO_EXCEPT) {return this->count_under(l, r, v+1) - this->count_under(l, r, v);}inline std::optional<T> next(const size_type l, const size_type r, const T& v, const size_type k) const noexcept(NO_EXCEPT) {const size_type rank = this->count_under(l, r, v) + k;return (rank < 0 or rank >= r - l) ? std::optional<T>{} : std::optional<T>(this->kth_smallest(l, r, rank));}inline std::optional<T> prev(const size_type l, const size_type r, const T& v, const size_type k) const noexcept(NO_EXCEPT) {const size_type rank = this->count_over(l, r, v) + k;return (rank < 0 or rank >= r - l) ? std::optional<T>{} : std::optional<T>(this->kth_largest(l, r, rank));}};}}template<class T, class dict_type = std::unordered_map<T,internal::size_t>> struct compressed_wavelet_matrix;template<class T, class dict_type = std::unordered_map<T,internal::size_t>>struct wavelet_matrix : internal::wavelet_matrix_impl::base<T,dict_type> {using compressed = compressed_wavelet_matrix<T,dict_type>;private:using base = typename internal::wavelet_matrix_impl::base<T,dict_type>;public:using value_type = T;using size_type = typename base::size_type;protected:inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {return p < 0 ? this->size() + p : p;}public:using base::base;bool empty() const noexcept(NO_EXCEPT) { return this->size() == 0; }inline T get(size_type p) const noexcept(NO_EXCEPT) {p = this->_positivize_index(p), assert(0 <= p && p < this->size());return this->base::get(p);}inline T operator[](const size_type p) const noexcept(NO_EXCEPT) { return this->get(p); }inline size_type select(const T& v, const size_type p) const noexcept(NO_EXCEPT) { return this->base::select(v, p); }struct iterator;struct range_reference;template<lib::interval rng = lib::interval::right_open>inline range_reference range(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {if constexpr(rng == lib::interval::right_open) return range_reference(this, l, r);if constexpr(rng == lib::interval::left_open) return range_reference(this, l+1, r+1);if constexpr(rng == lib::interval::open) return range_reference(this, l+1, r);if constexpr(rng == lib::interval::closed) return range_reference(this, l, r+1);}inline range_reference range() const noexcept(NO_EXCEPT) { return range_reference(this, 0, this->size()); }inline range_reference operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) { return range_reference(this, l, r); }inline range_reference subseq(const size_type p, const size_type c) const noexcept(NO_EXCEPT) { return range_reference(this, p, p+c); }inline range_reference subseq(const size_type p) const noexcept(NO_EXCEPT) { return range_reference(this, p, this->size()); }struct range_reference : internal::range_reference<const wavelet_matrix> {range_reference(const wavelet_matrix *const super, const size_type l, const size_type r) noexcept(NO_EXCEPT): internal::range_reference<const wavelet_matrix>(super, super->_positivize_index(l), super->_positivize_index(r)){assert(0 <= this->_begin && this->_begin <= this->_end && this->_end <= this->_super->size());}inline T get(const size_type k) const noexcept(NO_EXCEPT) {k = this->_super->_positivize_index(k);assert(0 <= k and k < this->size());return this->_super->get(this->_begin + k);}inline T operator[](const size_type k) const noexcept(NO_EXCEPT) { return this->get(k); }inline T kth_smallest(const size_type k) const noexcept(NO_EXCEPT) {assert(0 <= k && k < this->size());return this->_super->base::kth_smallest(this->_begin, this->_end, k);}inline auto kth_smallest_element(const size_type k) const noexcept(NO_EXCEPT) {if(k == this->size()) return this->end();assert(0 <= k && k < this->size());return std::next(this->_super->begin(), this->_super->base::kth_smallest_index(this->_begin, this->_end, k));}inline T kth_largest(const size_type k) const noexcept(NO_EXCEPT) {assert(0 <= k && k < this->size());return this->_super->base::kth_largest(this->_begin, this->_end, k);}inline auto kth_largest_element(const size_type k) const noexcept(NO_EXCEPT) {if(k == this->size()) return this->end();assert(0 <= k && k < this->size());return std::next(this->_super->begin(), this->_super->base::kth_largest_index(this->_begin, this->_end, k));}inline T min() const noexcept(NO_EXCEPT) { return this->kth_smallest(0); }inline T max() const noexcept(NO_EXCEPT) { return this->kth_largest(0); }inline T median() const noexcept(NO_EXCEPT) { return this->kth_smallest(this->size() / 2); }inline T sum_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->_super->base::sum_in_range(this->_begin, this->_end, x, y); }inline T sum_under(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::sum_under(this->_begin, this->_end, v); }inline T sum_over(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::sum_over(this->_begin, this->_end, v); }inline T sum_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::sum_or_under(this->_begin, this->_end, v); }inline T sum_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::sum_or_over(this->_begin, this->_end, v); }inline T sum(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->_super->base::sum_in_range(this->_begin, this->_end, x, y); }inline T sum() const noexcept(NO_EXCEPT) { return this->_super->base::sum(this->_begin, this->_end); }template<comp com>inline size_type sum(const T& v) const noexcept(NO_EXCEPT) {if constexpr(com == comp::under) return this->sum_under(v);if constexpr(com == comp::over) return this->sum_over(v);if constexpr(com == comp::or_under) return this->sum_or_under(v);if constexpr(com == comp::or_over) return this->sum_or_over(v);assert(false);}inline size_type count_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->_super->base::count_in_range(this->_begin, this->_end, x, y); }inline size_type count_under(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::count_under(this->_begin, this->_end, v); }inline size_type count_over(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::count_over(this->_begin, this->_end, v); }inline size_type count_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::count_or_under(this->_begin, this->_end, v); }inline size_type count_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->_super->base::count_or_over(this->_begin, this->_end, v); }template<comp com = comp::equal_to>inline size_type count(const T& v) const noexcept(NO_EXCEPT) {if constexpr(com == comp::eq) return this->_super->count_equal_to(this->_begin, this->_end, v);if constexpr(com == comp::under) return this->count_under(v);if constexpr(com == comp::over) return this->count_over(v);if constexpr(com == comp::or_under) return this->count_or_under(v);if constexpr(com == comp::or_over) return this->count_or_over(v);assert(false);}inline auto next_element(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {return this->kth_smallest_element(std::clamp(this->count_under(v) + k, 0, this->size()));}inline auto prev_element(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {return this->kth_smallest_element(std::clamp(this->count_over(v) - k, 0, this->size()));}inline std::optional<T> next(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->_super->base::next(this->_begin, this->_end, v, k); }inline std::optional<T> prev(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->_super->base::prev(this->_begin, this->_end, v, k); }};inline T kth_smallest(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_smallest(k); }inline T kth_smallest_element(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_smallest_element(k); }inline T kth_largest(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_largest(k); }inline T kth_largest_element(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_largest_element(k); }inline T min() const noexcept(NO_EXCEPT) { return this->range().kth_smallest(0); }inline T max() const noexcept(NO_EXCEPT) { return this->range().kth_largest(0); }inline T median() const noexcept(NO_EXCEPT) { return this->range().median(); }inline T sum_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->range().sum_in_range(x, y); }inline T sum_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().sum_under(v); }inline T sum_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().sum_over(v); }inline T sum_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().sum_or_under(v); }inline T sum_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().sum_or_over(v); }inline T sum(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->range().sum_in_range(x, y); }inline T sum() const noexcept(NO_EXCEPT) { return this->range().sum(); }template<comp com>inline size_type sum(const T& v) const noexcept(NO_EXCEPT) { return this->range().template sum<com>(v); }inline size_type count_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->range().count_in_range(x, y); }inline size_type count_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_under(v); }inline size_type count_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_over(v); }inline size_type count_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_or_under(v); }inline size_type count_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_or_over(v); }inline size_type count(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->range().count(x, y); }template<comp com = comp::equal_to>inline size_type count(const T& v) const noexcept(NO_EXCEPT) { return this->range().template count<com>(v); }inline auto next_element(const T& v) const noexcept(NO_EXCEPT) { return this->range().next_element(v); }inline auto prev_element(const T& v) const noexcept(NO_EXCEPT) { return this->range().prev_element(v); }inline std::optional<T> next(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->range().next(v, k); }inline std::optional<T> prev(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->range().prev(v, k); }protected:using iterator_interface = internal::container_iterator_interface<T,wavelet_matrix>;public:struct iterator : virtual iterator_interface {iterator(const wavelet_matrix *const ref, const size_type pos) noexcept(NO_EXCEPT) : iterator_interface(ref, pos) {}inline T operator*() const noexcept(NO_EXCEPT) { return this->ref()->get(this->pos()); }inline T operator[](const typename iterator_interface::difference_type count) const noexcept(NO_EXCEPT) { return *(*this + count); }};inline iterator begin() const noexcept(NO_EXCEPT) { return iterator(this, 0); }inline iterator end() const noexcept(NO_EXCEPT) { return iterator(this, this->size()); }};template<class T, class dict_type>struct compressed_wavelet_matrix : protected wavelet_matrix<typename compression<T>::size_type,dict_type> {protected:using core = wavelet_matrix<typename compression<T>::size_type,dict_type>;compression<T> compressed;public:using value_type = typename core::value_type;using size_type = typename core::size_type;template<class I> compressed_wavelet_matrix(const I first, const I last) noexcept(NO_EXCEPT) { this->build(first, last); }template<class I> void build(const I first, const I last) noexcept(NO_EXCEPT) {this->compressed = compression<T>(first, last);this->core::build(ALL(this->compressed));}inline T get(const size_type k) const noexcept(NO_EXCEPT) { return this->compressed(this->core::get(k)); }inline size_type operator[](const size_type k) const noexcept(NO_EXCEPT) { return this->core::get(k); }struct iterator;struct range_reference;template<lib::interval rng = lib::interval::right_open>inline range_reference range(const size_type l, const size_type r) const noexcept(NO_EXCEPT) {if constexpr(rng == lib::interval::right_open) return range_reference(this, l, r);if constexpr(rng == lib::interval::left_open) return range_reference(this, l+1, r+1);if constexpr(rng == lib::interval::open) return range_reference(this, l+1, r);if constexpr(rng == lib::interval::closed) return range_reference(this, l, r+1);}inline range_reference range() const noexcept(NO_EXCEPT) { return range_reference(this, 0, this->size()); }inline range_reference operator()(const size_type l, const size_type r) const noexcept(NO_EXCEPT) { return range_reference(this, l, r); }inline range_reference subseq(const size_type p, const size_type c) const noexcept(NO_EXCEPT) { return range_reference(this, p, p+c); }inline range_reference subseq(const size_type p) const noexcept(NO_EXCEPT) { return range_reference(this, p, this->size()); }struct range_reference : internal::range_reference<const compressed_wavelet_matrix> {range_reference(const compressed_wavelet_matrix *const super, const size_type l, const size_type r) noexcept(NO_EXCEPT): internal::range_reference<const compressed_wavelet_matrix>(super, super->_positivize_index(l), super->_positivize_index(r)){assert(0 <= this->_begin && this->_begin <= this->_end && this->_end <= this->_super->size());}private:inline auto _range() const noexcept(NO_EXCEPT) { return this->_super->core::range(this->_begin, this->_end); }public:inline T get(const size_type k) const noexcept(NO_EXCEPT) { return this->_super->compressed(this->_range().get(k)); }inline T operator[](const size_type k) const noexcept(NO_EXCEPT) { return this->get(k); }inline T kth_smallest(const size_type k) const noexcept(NO_EXCEPT) { return this->_super->compressed(this->_range().kth_smallest(k)); }inline auto kth_smallest_element(const size_type k) const noexcept(NO_EXCEPT) {return std::next(this->_super->begin(), std::distance(this->_super->core::begin(), this->_range().kth_smallest_element(k)));}inline T kth_largest(const size_type k) const noexcept(NO_EXCEPT) { return this->_super->compressed(this->_range().kth_largest(k));}inline auto kth_largest_element(const size_type k) const noexcept(NO_EXCEPT) {return std::next(this->_super->begin(), std::distance(this->_super->core::begin(), this->_range().kth_largest_element(k)));}inline T min() const noexcept(NO_EXCEPT) { return this->kth_smallest(0); }inline T max() const noexcept(NO_EXCEPT) { return this->kth_largest(0); }inline T median() const noexcept(NO_EXCEPT) { return this->kth_smallest(this->size() / 2); }inline size_type count_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) {return this->_range().count_in_range(this->_super->compressed.rank(x), this->_super->compressed.rank(y));}inline size_type count_under(const T& v) const noexcept(NO_EXCEPT) { return this->_range().count_under(this->_super->compressed.rank(v)); }inline size_type count_over(const T& v) const noexcept(NO_EXCEPT) { return this->_range().count_over(this->_super->compressed.rank2(v)); }inline size_type count_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->_range().count_or_under(this->_super->compressed.rank2(v)); }inline size_type count_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->_range().count_or_over(this->_super->compressed.rank(v)); }template<comp com = comp::equal_to>inline size_type count(const T& v) const noexcept(NO_EXCEPT) { return this->_range().template count<com>(this->_super->compressed.rank(v)); }inline auto next_element(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {return this->kth_smallest_element(std::clamp(this->_range().count_under(this->_super->compressed.rank(v) + k), 0, this->size()));}inline auto prev_element(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {return this->kth_largest_element(std::clamp(this->_range().count_over(this->_super->compressed.rank2(v) + k), 0, this->size()));}inline std::optional<T> next(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {const std::optional<size_type> res = this->_range().next(this->_super->compressed.rank(v), k);if(res.has_value()) return this->_super->compressed(res.value());return {};}inline std::optional<T> prev(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) {const std::optional<size_type> res = this->_range().prev(this->_super->compressed.rank2(v), k);if(res.has_value()) return this->_super->compressed(res.value());return {};}};inline T kth_smallest(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_smallest(k); }inline auto kth_smallest_element(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_smallest_element(k); }inline T kth_largest(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_largest(k); }inline auto kth_largest_element(const size_type k) const noexcept(NO_EXCEPT) { return this->range().kth_largest_element(k); }inline T min() const noexcept(NO_EXCEPT) { return this->range().kth_smallest(0); }inline T max() const noexcept(NO_EXCEPT) { return this->range().kth_largest(0); }inline T median() const noexcept(NO_EXCEPT) { return this->range().median(); }inline size_type count_in_range(const T& x, const T& y) const noexcept(NO_EXCEPT) { return this->range().count_in_range(x, y); }inline size_type count_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_under(v); }inline size_type count_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_over(v); }inline size_type count_or_under(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_or_under(v); }inline size_type count_or_over(const T& v) const noexcept(NO_EXCEPT) { return this->range().count_or_over(v); }template<comp com = comp::equal_to> inline size_type count(const T& v) const noexcept(NO_EXCEPT) { return this->range().template count<com>(v); }inline auto next_element(const T& v) const noexcept(NO_EXCEPT) { return this->range().next_element(v); }inline auto prev_element(const T& v) const noexcept(NO_EXCEPT) { return this->range().prev_element(v); }inline std::optional<T> next(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->range().next(v, k); }inline std::optional<T> prev(const T& v, const size_type k = 0) const noexcept(NO_EXCEPT) { return this->range().prev(v, k); }protected:using iterator_interface = internal::container_iterator_interface<T,compressed_wavelet_matrix>;public:struct iterator : virtual iterator_interface {iterator(const compressed_wavelet_matrix *const ref, const size_type pos) noexcept(NO_EXCEPT) : iterator_interface(ref, pos) {}inline T operator*() const noexcept(NO_EXCEPT) { return this->ref()->get(this->pos()); }inline T operator[](const typename iterator_interface::difference_type count) const noexcept(NO_EXCEPT) { return *(*this + count); }};inline iterator begin() const noexcept(NO_EXCEPT) { return iterator(this, 0); }inline iterator end() const noexcept(NO_EXCEPT) { return iterator(this, this->size()); }};}
/* [data_structure/wavelet_matrix.hpp] */


signed main() {
    int n, k; std::cin >> n >> k;
    std::vector<long> a(n); ITRR(v, a) std::cin >> v;
    lib::wavelet_matrix<long> data(ALL(a));

    long ans = lib::INF64;
    FOR(i, 0, n-k) {
        auto range = data.subseq(i, k);
        // debug(range);

        long med = range.median();

        long costl = med * range.count_under(med) - range.sum_under(med);
        long costr = range.sum_or_over(med) - med * range.count_or_over(med);

        lib::chmin(ans, costl + costr);
    }

    std::cout << ans << "\n";
}
yukicoder

結果

テストケース

ソースコード
