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

提出ソース
結果

問題	No.738 平らな農地
ユーザー	🦠みどりむし
提出日時	2023-06-10 15:17:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	307 ms / 2,000 ms
コード長	51,152 bytes
コンパイル時間	2,540 ms
コンパイル使用メモリ	247,552 KB
実行使用メモリ	34,964 KB
最終ジャッジ日時	2024-06-10 21:49:39
合計ジャッジ時間	15,260 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	7 ms 5,376 KB
testcase_06	AC	8 ms 5,376 KB
testcase_07	AC	6 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	4 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	6 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	169 ms 30,304 KB
testcase_16	AC	175 ms 30,852 KB
testcase_17	AC	196 ms 30,704 KB
testcase_18	AC	190 ms 30,156 KB
testcase_19	AC	235 ms 32,368 KB
testcase_20	AC	174 ms 30,848 KB
testcase_21	AC	217 ms 32,632 KB
testcase_22	AC	177 ms 31,116 KB
testcase_23	AC	215 ms 31,548 KB
testcase_24	AC	215 ms 31,120 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	3 ms 5,376 KB
testcase_29	AC	3 ms 5,376 KB
testcase_30	AC	4 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	4 ms 5,376 KB
testcase_33	AC	3 ms 5,376 KB
testcase_34	AC	4 ms 5,376 KB
testcase_35	AC	3 ms 5,376 KB
testcase_36	AC	3 ms 5,376 KB
testcase_37	AC	3 ms 5,376 KB
testcase_38	AC	3 ms 5,376 KB
testcase_39	AC	3 ms 5,376 KB
testcase_40	AC	3 ms 5,376 KB
testcase_41	AC	3 ms 5,376 KB
testcase_42	AC	3 ms 5,376 KB
testcase_43	AC	3 ms 5,376 KB
testcase_44	AC	3 ms 5,376 KB
testcase_45	AC	170 ms 33,172 KB
testcase_46	AC	167 ms 30,560 KB
testcase_47	AC	166 ms 32,180 KB
testcase_48	AC	147 ms 31,116 KB
testcase_49	AC	144 ms 30,840 KB
testcase_50	AC	144 ms 32,080 KB
testcase_51	AC	171 ms 32,360 KB
testcase_52	AC	157 ms 30,844 KB
testcase_53	AC	161 ms 31,644 KB
testcase_54	AC	175 ms 32,492 KB
testcase_55	AC	175 ms 32,480 KB
testcase_56	AC	168 ms 32,064 KB
testcase_57	AC	155 ms 30,548 KB
testcase_58	AC	163 ms 31,800 KB
testcase_59	AC	160 ms 33,052 KB
testcase_60	AC	156 ms 32,772 KB
testcase_61	AC	155 ms 32,764 KB
testcase_62	AC	150 ms 30,556 KB
testcase_63	AC	177 ms 33,048 KB
testcase_64	AC	166 ms 32,760 KB
testcase_65	AC	248 ms 30,852 KB
testcase_66	AC	258 ms 31,824 KB
testcase_67	AC	209 ms 32,608 KB
testcase_68	AC	197 ms 33,440 KB
testcase_69	AC	286 ms 33,992 KB
testcase_70	AC	236 ms 34,964 KB
testcase_71	AC	27 ms 8,576 KB
testcase_72	AC	163 ms 28,672 KB
testcase_73	AC	145 ms 27,008 KB
testcase_74	AC	199 ms 29,952 KB
testcase_75	AC	263 ms 32,472 KB
testcase_76	AC	211 ms 33,444 KB
testcase_77	AC	278 ms 32,472 KB
testcase_78	AC	307 ms 34,692 KB
testcase_79	AC	299 ms 34,832 KB
testcase_80	AC	233 ms 33,720 KB
testcase_81	AC	263 ms 32,884 KB
testcase_82	AC	279 ms 34,124 KB
testcase_83	AC	182 ms 31,232 KB
testcase_84	AC	157 ms 30,336 KB
testcase_85	AC	297 ms 34,696 KB
testcase_86	AC	271 ms 32,468 KB
testcase_87	AC	89 ms 33,724 KB
testcase_88	AC	84 ms 32,464 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	1 ms 5,376 KB
testcase_91	AC	1 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #include <bits/stdc++.h>
// #include "template.hpp"
#include <iostream>
/* #expanded [adapter/io.hpp] */
/* #expanded [adapter/input.hpp] */
#include <atcoder/modint>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
/* #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/resolving_rank.hpp] */
namespace lib {namespace internal {template<int P> struct resolving_rank : resolving_rank<P-1> {};template<> struct resolving_rank<0> {};}}
/* [internal/resolving_rank.hpp] */
template<class source = std::istream>struct input_adapter {private:template<class T>auto _set(lib::internal::resolving_rank<3>, T *const val) noexcept(NO_EXCEPT) -> decltype(std::declval<source&>() >> *val, 0) {*this->in >> *val;return 0;}template<class T>auto _set(lib::internal::resolving_rank<2>, T *const val) noexcept(NO_EXCEPT) -> decltype(std::begin(*val), std::end(*val), 0) {(*this)(std::begin(*val), std::end(*val));return 0;}template<class T>auto _set(lib::internal::resolving_rank<1>, T *const val) noexcept(NO_EXCEPT) -> decltype(val->first, val->second, 0) {(*this)(&*val);return 0;}template<class T>auto _set(lib::internal::resolving_rank<0>, T *const val) noexcept(NO_EXCEPT) -> std::enable_if_t<atcoder::internal::is_modint<T>::value,int> {long long v; std::cin >> v;*val = { v };return 0;}protected:template<class T>source *set(T *const val) noexcept(NO_EXCEPT) {this->_set(lib::internal::resolving_rank<3>{}, val);return this->in;}public:using char_type = typename source::char_type;source *in;input_adapter(source *_in = &std::cin) noexcept(NO_EXCEPT) : in(_in) {}template<class T> inline input_adapter& operator>>(T &s) noexcept(NO_EXCEPT) {this->set(&s);return *this;}template<class T> inline T one() noexcept(NO_EXCEPT) {T val; *this >> val;return val;}template<class T> inline void operator()(T*const val) noexcept(NO_EXCEPT) {*this >> *val;}template<class T, class... Args> inline void operator()(T *const head, Args *const... tail) noexcept(NO_EXCEPT) {*this >> *head;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::value_type> inline void operator()(I first, I last) noexcept(NO_EXCEPT) {for(I itr=first; itr!=last; ++itr) *this >> *itr;}template<class F, class S> inline void operator()(std::pair<F,S> *const p) noexcept(NO_EXCEPT) {*this >> p->first >> p->second;}};
/* [adapter/input.hpp] */
/* #expanded [adapter/output.hpp] */
#include <iomanip>
template<class destination = std::ostream, class Terminator = std::string, class Separator = std::string>struct output_adapter {private:template<class T>auto _put(lib::internal::resolving_rank<2>, const T &val) noexcept(NO_EXCEPT)-> decltype(std::declval<destination&>() << val, 0) {*this->out << val;return 0;}template<class T>auto _put(lib::internal::resolving_rank<1>, const T &val) noexcept(NO_EXCEPT)-> decltype(val.val(), 0) {this->put(val.val());return 0;}template<class T>auto _put(lib::internal::resolving_rank<0>, const T &val) noexcept(NO_EXCEPT)-> decltype(std::begin(val), std::end(val), 0) {(*this)(std::begin(val), std::end(val), false);return 0;}protected:template<class T>destination *put(const T &val) noexcept(NO_EXCEPT){this->_put(lib::internal::resolving_rank<2>{}, val);return this->out;}public:using char_type = typename destination::char_type;static constexpr auto sendl = std::endl<char_type,std::char_traits<char_type>>;destination *out;Terminator endline;Separator separator;output_adapter(destination *des = &std::cout, Terminator endl = "\n", Separator sep = " ") noexcept: out(des), endline(endl), separator(sep){*this << std::fixed << std::setprecision(20);}inline void seekp(const typename destination::off_type off, const std::ios_base::seekdir dir = std::ios_base::cur) noexcept(NO_EXCEPT){ this->out->seekp(off, dir); };template<class T> inline output_adapter& operator<<(const T &s) noexcept(NO_EXCEPT){this->put(s);return *this;}template<class T = std::string> inline void operator()(const T &val = "") noexcept(NO_EXCEPT){*this << val << this->endline;}template<class T, class ...Args> inline void operator()(const T &head, const Args& ...tail) noexcept(NO_EXCEPT){*this << head << this->separator;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::iterator_category> inline void operator()(const I first, const I last, const bool terminate = true) noexcept(NO_EXCEPT){for(I itr=first; itr!=last;) {*this << *itr;if(++itr == last) {if(terminate) *this << this->endline;}else *this << this->separator;}}template<class T> inline void operator()(const std::initializer_list<T> vals) noexcept(NO_EXCEPT){std::vector wrapped(vals.begin(), vals.end());(*this)(wrapped.begin(), wrapped.end());}template<class F, class S> inline void operator()(const std::pair<F,S> &p) noexcept(NO_EXCEPT){(*this)(p.first, p.second);}};
/* [adapter/output.hpp] */
input_adapter _input;output_adapter _print;
#define input _input
#define print _print
/* [adapter/io.hpp] */
/* #expanded [utility/functional.hpp] */
#include <functional>
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 <unordered_map>
#include <algorithm>
#include <array>
#include <optional>
#include <limits>
/* #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; input >> n >> k;
    std::vector<long> a(n); input >> a;
    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);
    }

    print(ans);
}
yukicoder

結果

テストケース

ソースコード
