結果
| 問題 | No.738 平らな農地 |
| ユーザー |
 kakao745
|
| 提出日時 | 2024-09-07 16:10:19 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 989 ms / 2,000 ms |
| コード長 | 30,606 bytes |
| コンパイル時間 | 5,015 ms |
| コンパイル使用メモリ | 320,768 KB |
| 実行使用メモリ | 35,856 KB |
| 最終ジャッジ日時 | 2024-09-07 16:11:01 |
| 合計ジャッジ時間 | 41,106 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,944 KB |
| testcase_02 | AC | 2 ms
6,944 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 16 ms
6,940 KB |
| testcase_06 | AC | 19 ms
6,944 KB |
| testcase_07 | AC | 12 ms
6,944 KB |
| testcase_08 | AC | 8 ms
6,944 KB |
| testcase_09 | AC | 5 ms
6,940 KB |
| testcase_10 | AC | 3 ms
6,944 KB |
| testcase_11 | AC | 7 ms
6,940 KB |
| testcase_12 | AC | 5 ms
6,940 KB |
| testcase_13 | AC | 21 ms
6,944 KB |
| testcase_14 | AC | 7 ms
6,940 KB |
| testcase_15 | AC | 570 ms
30,984 KB |
| testcase_16 | AC | 514 ms
31,388 KB |
| testcase_17 | AC | 620 ms
31,128 KB |
| testcase_18 | AC | 605 ms
30,588 KB |
| testcase_19 | AC | 751 ms
32,892 KB |
| testcase_20 | AC | 527 ms
31,404 KB |
| testcase_21 | AC | 709 ms
33,152 KB |
| testcase_22 | AC | 540 ms
31,532 KB |
| testcase_23 | AC | 710 ms
32,076 KB |
| testcase_24 | AC | 697 ms
31,788 KB |
| testcase_25 | AC | 5 ms
6,944 KB |
| testcase_26 | AC | 6 ms
6,940 KB |
| testcase_27 | AC | 5 ms
6,944 KB |
| testcase_28 | AC | 5 ms
6,940 KB |
| testcase_29 | AC | 5 ms
6,940 KB |
| testcase_30 | AC | 6 ms
6,944 KB |
| testcase_31 | AC | 5 ms
6,944 KB |
| testcase_32 | AC | 5 ms
6,944 KB |
| testcase_33 | AC | 5 ms
6,944 KB |
| testcase_34 | AC | 5 ms
6,944 KB |
| testcase_35 | AC | 5 ms
6,944 KB |
| testcase_36 | AC | 5 ms
6,944 KB |
| testcase_37 | AC | 5 ms
6,940 KB |
| testcase_38 | AC | 5 ms
6,944 KB |
| testcase_39 | AC | 6 ms
6,944 KB |
| testcase_40 | AC | 5 ms
6,944 KB |
| testcase_41 | AC | 6 ms
6,940 KB |
| testcase_42 | AC | 5 ms
6,940 KB |
| testcase_43 | AC | 5 ms
6,940 KB |
| testcase_44 | AC | 5 ms
6,940 KB |
| testcase_45 | AC | 473 ms
34,072 KB |
| testcase_46 | AC | 483 ms
31,372 KB |
| testcase_47 | AC | 473 ms
32,992 KB |
| testcase_48 | AC | 398 ms
31,916 KB |
| testcase_49 | AC | 397 ms
31,644 KB |
| testcase_50 | AC | 400 ms
32,992 KB |
| testcase_51 | AC | 503 ms
33,260 KB |
| testcase_52 | AC | 451 ms
31,772 KB |
| testcase_53 | AC | 470 ms
32,188 KB |
| testcase_54 | AC | 500 ms
33,260 KB |
| testcase_55 | AC | 518 ms
33,260 KB |
| testcase_56 | AC | 496 ms
32,724 KB |
| testcase_57 | AC | 450 ms
31,228 KB |
| testcase_58 | AC | 460 ms
32,636 KB |
| testcase_59 | AC | 446 ms
34,072 KB |
| testcase_60 | AC | 429 ms
33,788 KB |
| testcase_61 | AC | 435 ms
33,652 KB |
| testcase_62 | AC | 436 ms
31,248 KB |
| testcase_63 | AC | 525 ms
34,032 KB |
| testcase_64 | AC | 481 ms
33,404 KB |
| testcase_65 | AC | 966 ms
31,516 KB |
| testcase_66 | AC | 989 ms
32,604 KB |
| testcase_67 | AC | 576 ms
33,036 KB |
| testcase_68 | AC | 532 ms
33,976 KB |
| testcase_69 | AC | 912 ms
34,644 KB |
| testcase_70 | AC | 692 ms
35,724 KB |
| testcase_71 | AC | 31 ms
8,072 KB |
| testcase_72 | AC | 547 ms
29,060 KB |
| testcase_73 | AC | 363 ms
27,528 KB |
| testcase_74 | AC | 603 ms
30,316 KB |
| testcase_75 | AC | 832 ms
32,768 KB |
| testcase_76 | AC | 610 ms
34,108 KB |
| testcase_77 | AC | 963 ms
32,892 KB |
| testcase_78 | AC | 962 ms
35,692 KB |
| testcase_79 | AC | 910 ms
35,856 KB |
| testcase_80 | AC | 665 ms
34,508 KB |
| testcase_81 | AC | 820 ms
33,432 KB |
| testcase_82 | AC | 794 ms
34,652 KB |
| testcase_83 | AC | 548 ms
31,760 KB |
| testcase_84 | AC | 520 ms
30,700 KB |
| testcase_85 | AC | 964 ms
35,460 KB |
| testcase_86 | AC | 890 ms
32,700 KB |
| testcase_87 | AC | 152 ms
34,376 KB |
| testcase_88 | AC | 146 ms
32,756 KB |
| testcase_89 | AC | 2 ms
6,944 KB |
| testcase_90 | AC | 2 ms
6,940 KB |
| testcase_91 | AC | 2 ms
6,944 KB |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define rep(i,n) for(long long i=0;i<(long long)n;i++)
#define reps(i,n) for(long long i=1;i<=(long long)n;i++)
#define loop(i,l,r) for(long long i=l;i<=(long long)r;i++)
#define drep(i,n) for(long long i=(long long)n-1;i>=0;i--)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yn(x) cout << (x? "Yes":"No") << endl;
#define cou(x) cout << x << endl;
#define emp emplace_back
//#pragma GCC target ("avx,avx2")//四則演算
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")//ループ
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//浮動小数点
const long long mod=998244353LL;
const long long mods=1000000007LL;
const double inf=numeric_limits<double>::infinity();
const int kaz=1000000000;
const long long yab=2500000000000000000LL;
const long long aho =-yab;
const long double eps=1.0e-14L;
const long double pi=acosl(-1.0L);
using ll=long long;
using st=string;
using P=pair<ll,ll>;
using tup=tuple<ll,ll,ll>;
using vi=vector<ll>;
using vin=vector<int>;
using vc=vector<char>;
using vb=vector<bool>;
using vd=vector<double>;
using vs=vector<string>;
using vp=vector<P>;
using sp=set<P>;
using si=set<ll>;
using vvi=vector<vector<ll>>;
using vvin=vector<vin>;
using vvc=vector<vc>;
using vvb=vector<vb>;
using vvvi=vector<vvi>;
using vvvin=vector<vvin>;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const vector<int> ex = {-1, -1, -1, 0, 0, 1, 1, 1};
const vector<int> ey = {-1, 0, 1, -1, 1, -1, 0, 1};
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,v.size())os<<v[i]<<(i+1!=v.size()?" ":"\n");return os;}
template<typename T1,typename T2>
void co(bool x,T1 y,T2 z){
if(x)cout << y << endl;
else cout << z << endl;
}
template<typename T>
bool chmax(T &a, T b){
if(a<b){
a=b;
return true;
}
return false;
}
template<typename T>
bool chmin(T &a, T b){
if(a>b){
a=b;
return true;
}
return false;
}
template<typename T>
void print(vector<T> &a){
for(int i=0;i<a.size();i++){
cout << a[i];
if(i==(long long)a.size()-1)cout << endl;
else cout << " ";
}
}
ll mypow(ll x,ll y){
ll ret=1;
while(y>0){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
//wavelet matrix
//1-indexed(ちゅうい！)??
enum {
NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU
};
class SuccinctBitVector {
private:
const uint64_t size; // ビットベクトルのサイズ
static const uint64_t blockBitNum = 16;
static const uint64_t LEVEL_L = 512;
static const uint64_t LEVEL_S = 16;
std::vector<uint64_t> L; // 大ブロック
std::vector<uint16_t> S; // 小ブロック
std::vector<uint16_t> B; // ビットベクトル
uint64_t numOne = 0; // 1bitの数
public:
explicit SuccinctBitVector(const uint64_t n) : size(n) {
const uint64_t s = (n + blockBitNum - 1) / blockBitNum + 1; // ceil(n, blockSize)
this->B.assign(s, 0);
this->L.assign(n / LEVEL_L + 1, 0);
this->S.assign(n / LEVEL_S + 1, 0);
}
// B[pos] = bit
void setBit(const uint64_t bit, const uint64_t pos){
assert(bit == 0 or bit == 1);
assert(pos < this->size);
const uint64_t blockPos = pos / blockBitNum;
const uint64_t offset = pos % blockBitNum;
if (bit == 1) { B.at(blockPos) |= (1LLU << offset); }
else { B.at(blockPos) &= (~(1LLU << offset)); }
}
// B[pos]
uint64_t access(const uint64_t pos) {
assert(pos < this->size);
const uint64_t blockPos = pos / blockBitNum;
const uint64_t offset = pos % blockBitNum;
return ((B.at(blockPos) >> offset) & 1);
}
void build() {
uint64_t num = 0;
for (uint64_t i = 0; i <= size; i++){
if (i % LEVEL_L == 0) {
L.at(i / LEVEL_L) = num;
}
if (i % LEVEL_S == 0) {
S.at(i / LEVEL_S) = num - L.at(i / LEVEL_L);
}
if (i != size and i % blockBitNum == 0) {
num += this->popCount(this->B.at(i / blockBitNum));
}
}
this-> numOne = num;
}
// B[0, pos)のbitの数
uint64_t rank(const uint64_t bit, const uint64_t pos) {
assert(bit == 0 or bit == 1);
assert(pos <= this->size);
if (bit) {
return L[pos / LEVEL_L] + S[pos / LEVEL_S] + popCount(B[pos / blockBitNum] & ((1 << (pos % blockBitNum)) - 1));
}
else {
return pos - rank(1, pos);
}
}
// rank番目のbitの位置 + 1(rankは1-origin)
uint64_t select(const uint64_t bit, const uint64_t rank) {
assert(bit == 0 or bit == 1);
assert(rank > 0);
if (bit == 0 and rank > this->size - this-> numOne) { return NOTFOUND; }
if (bit == 1 and rank > this-> numOne) { return NOTFOUND; }
// 大ブロックL内を検索
uint64_t large_idx = 0;
{
uint64_t left = 0;
uint64_t right = L.size();
while (right - left > 1) {
uint64_t mid = (left + right) / 2;
uint64_t r = L.at(mid);
r = (bit) ? r : mid * LEVEL_L - L.at(mid);
if (r < rank) {
left = mid;
large_idx = mid;
} else {
right = mid;
}
}
}
// 小ブロックS内を検索
uint64_t small_idx = (large_idx * LEVEL_L) / LEVEL_S;
{
uint64_t left = (large_idx * LEVEL_L) / LEVEL_S;
uint64_t right = std::min(((large_idx + 1) * LEVEL_L) / LEVEL_S, (uint64_t)S.size());
while (right - left > 1) {
uint64_t mid = (left + right) / 2;
uint64_t r = L.at(large_idx) + S.at(mid);
r = (bit) ? r :mid * LEVEL_S - r;
if (r < rank) {
left = mid;
small_idx = mid;
} else {
right = mid;
}
}
}
// Bをブロック単位で順番に探索
uint64_t rank_pos = 0;
{
const uint64_t begin_block_idx = (small_idx * LEVEL_S) / blockBitNum;
uint64_t total_bit = L.at(large_idx) + S.at(small_idx);
if (bit == 0) {
total_bit = small_idx * LEVEL_S - total_bit;
}
for (uint64_t i = 0;; ++i) {
uint64_t b = popCount(B.at(begin_block_idx + i));
if (bit == 0) {
b = blockBitNum - b;
}
if (total_bit + b >= rank) {
uint64_t block = (bit) ? B.at(begin_block_idx + i) : ~B.at(begin_block_idx + i);
rank_pos = (begin_block_idx + i) * blockBitNum + selectInBlock(block, rank - total_bit);
break;
}
total_bit += b;
}
}
return rank_pos + 1;
}
uint64_t getNumOne() const {
return numOne;
}
void debug() {
std::cout << "LEVEL_L(" << L.size() << ")" << std::endl;
for (uint64_t i = 0 ; i < L.size(); ++i) {
std::cout << L.at(i) << ", ";
}
std::cout << std::endl;
std::cout << "LEVEL_S(" << S.size() << ")" << std::endl;
for (uint64_t i = 0 ; i < S.size(); ++i) {
std::cout << S.at(i) << ", ";
}
std::cout << std::endl;
}
private:
uint64_t popCount(uint64_t x) {
x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0x7FLLU;
}
uint64_t selectInBlock(uint64_t x, uint64_t rank) {
uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);
uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);
uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;
uint64_t pos = 0;
for (;; pos += 8){
uint64_t rank_next = (x3 >> pos) & 0xFFLLU;
if (rank <= rank_next) break;
rank -= rank_next;
}
uint64_t v2 = (x2 >> pos) & 0xFLLU;
if (rank > v2) {
rank -= v2;
pos += 4;
}
uint64_t v1 = (x1 >> pos) & 0x3LLU;
if (rank > v1){
rank -= v1;
pos += 2;
}
uint64_t v0 = (x >> pos) & 0x1LLU;
if (v0 < rank){
rank -= v0;
pos += 1;
}
return pos;
}
};
class WaveletMatrix {
private:
std::vector<SuccinctBitVector> bit_arrays;
std::vector<uint64_t> begin_one; // 各bitに着目したときの1の開始位置
std::map<uint64_t, uint64_t> begin_alphabet; // 最後のソートされた配列で各文字の開始位置
std::vector<std::vector<uint64_t>> cumulative_sum; // 各bitに着目したときの累積和
uint64_t size; // 与えられた配列のサイズ
uint64_t maximum_element; // 文字数
uint64_t bit_size; // 文字を表すのに必要なbit数
public:
WaveletMatrix (const std::vector<uint64_t> &array) {
assert(array.size() > 0);
size = array.size();
maximum_element = *max_element(array.begin(), array.end()) + 1;
bit_size = get_num_of_bit(maximum_element);
if (bit_size == 0) {
bit_size = 1;
}
for (uint64_t i = 0; i < bit_size; ++i) {
SuccinctBitVector sv(size);
bit_arrays.push_back(sv);
}
this->begin_one.resize(bit_size);
this->cumulative_sum.resize(bit_size + 1, std::vector<uint64_t>(size + 1, 0));
for (uint64_t j = 0; j < array.size(); ++j) {
this->cumulative_sum.at(0).at(j + 1) = this->cumulative_sum.at(0).at(j) + array[j];
}
std::vector<uint64_t> v(array);
for (uint64_t i = 0; i < bit_size; ++i) {
std::vector<uint64_t> temp;
// 0をtempにいれてく
for (uint64_t j = 0; j < v.size(); ++j) {
uint64_t c = v.at(j);
uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit
if (bit == 0) {
temp.push_back(c);
bit_arrays.at(i).setBit(0, j);
}
}
this->begin_one.at(i) = temp.size();
// 1をtempにいれてく
for (uint64_t j = 0; j < v.size(); ++j) {
uint64_t c = v.at(j);
uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit
if (bit == 1) {
temp.push_back(c);
bit_arrays.at(i).setBit(1, j);
}
}
for (uint64_t j = 0; j < temp.size(); ++j) {
this->cumulative_sum.at(i + 1).at(j + 1) = this->cumulative_sum.at(i + 1).at(j) + temp.at(j);
}
bit_arrays.at(i).build();
v = temp;
}
// ソートされた配列内での各文字の位置を取得
for (int i = v.size() - 1; i >= 0; --i) {
this->begin_alphabet[v.at(i)] = i;
}
}
// v[pos]
uint64_t access(uint64_t pos) {
if (pos >= this->size) { return NOTFOUND; }
uint64_t c = 0;
for (uint64_t i = 0; i < bit_arrays.size(); ++i) {
uint64_t bit = bit_arrays.at(i).access(pos); // もとの数値のi番目のbit
c = (c <<= 1) | bit;
pos = bit_arrays.at(i).rank(bit, pos);
if (bit) {
pos += this->begin_one.at(i);
}
}
return c;
}
// i番目のcの位置 + 1を返す。rankは1-origin
uint64_t select(uint64_t c, uint64_t rank) {
assert(rank > 0);
if (c >= maximum_element) {
return NOTFOUND;
}
if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {
return NOTFOUND;
}
uint64_t index = this->begin_alphabet.at(c) + rank;
for (uint64_t i = 0; i < bit_arrays.size(); ++i){
uint64_t bit = ((c >> i) & 1); // 下からi番目のbit
if (bit == 1) {
index -= this->begin_one.at(bit_size - i - 1);
}
index = this->bit_arrays.at(bit_size - i - 1).select(bit, index);
}
return index;
}
// v[begin_pos, end_pos)で最大値のindexを返す
uint64_t maxRange(uint64_t begin_pos, uint64_t end_pos) {
return quantileRange(begin_pos, end_pos, end_pos - begin_pos - 1);
}
// v[begin_pos, end_pos)で最小値のindexを返す
uint64_t minRange(uint64_t begin_pos, uint64_t end_pos) {
return quantileRange(begin_pos, end_pos, 0);
}
// v[begin_pos, end_pos)でk番目に小さい数値のindexを返す(kは0-origin)
// つまり小さい順に並べてk番目の値
uint64_t quantileRange(uint64_t begin_pos, uint64_t end_pos, uint64_t k) {
if ((end_pos > size || begin_pos >= end_pos) || (k >= end_pos - begin_pos)) {
return NOTFOUND;
}
uint64_t val = 0;
for (uint64_t i = 0; i < bit_size; ++i) {
const uint64_t num_of_zero_begin = bit_arrays.at(i).rank(0, begin_pos);
const uint64_t num_of_zero_end = bit_arrays.at(i).rank(0, end_pos);
const uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin; // beginからendまでにある0の数
const uint64_t bit = (k < num_of_zero) ? 0 : 1; // k番目の値の上からi番目のbitが0か1か
if (bit) {
k -= num_of_zero;
begin_pos = this->begin_one.at(i) + begin_pos - num_of_zero_begin;
end_pos = this->begin_one.at(i) + end_pos - num_of_zero_end;
}
else {
begin_pos = num_of_zero_begin;
end_pos = num_of_zero_begin + num_of_zero;
}
val = ((val << 1) | bit);
}
uint64_t left = 0;
for (uint64_t i = 0; i < bit_size; ++i) {
const uint64_t bit = (val >> (bit_size - i - 1)) & 1; // 上からi番目のbit
left = bit_arrays.at(i).rank(bit, left); // cのi番目のbitと同じ数値の数
if (bit) {
left += this->begin_one.at(i);
}
}
const uint64_t rank = begin_pos + k - left + 1;
return select(val, rank) - 1;
}
uint64_t top_k_sum(uint64_t k, uint64_t l,uint64_t r) {
if (l == r) return 0;
uint64_t res = 0, val = 0;
for (int i = 0; i < bit_size; ++i) {
const int j = bit_arrays[i].rank(0,r)-bit_arrays[i].rank(0,l);
if (j > k) {
l = bit_arrays[i].rank(0,l);
r = bit_arrays[i].rank(0,r);
} else {
uint64_t l2 = bit_arrays[i].rank(0,l);
uint64_t r2 = bit_arrays[i].rank(0,r);
res += cumulative_sum[i + 1][r2] - cumulative_sum[i + 1][l2];
l = begin_one[i] + bit_arrays[i].rank(1,l);
r = begin_one[i] + bit_arrays[i].rank(1,r);
k -= j;
val |= (1LL << (bit_size - i - 1));
}
}
res += val * k;
return res;
}
// v[0, pos)のcの数
uint64_t rank(uint64_t c, uint64_t pos) {
assert(pos < size);
if (c >= maximum_element) {
return 0;
}
if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {
return 0;
}
for (uint64_t i = 0; i < bit_size; ++i) {
uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit
pos = bit_arrays.at(i).rank(bit, pos); // cのi番目のbitと同じ数値の数
if (bit) {
pos += this->begin_one.at(i);
}
}
uint64_t begin_pos = this->begin_alphabet.at(c);
return pos - begin_pos;
}
// v[begin_pos, end_pos)で[min, max)に入る値の個数
uint64_t rangeFreq(uint64_t begin_pos, uint64_t end_pos, uint64_t min_c, uint64_t max_c) {
if ((end_pos > size || begin_pos >= end_pos) || (min_c >= max_c) || min_c >= maximum_element) {
return 0;
}
const auto maxi_t = rankAll(max_c, begin_pos, end_pos);
const auto mini_t = rankAll(min_c, begin_pos, end_pos);
return std::get<1>(maxi_t) - std::get<1>(mini_t);
}
// v[0, pos)でcより小さい文字の数
uint64_t rankLessThan(uint64_t c, uint64_t begin, uint64_t end) {
auto t = rankAll(c, begin, end);
return std::get<1>(t);
}
// v[0, pos)でcより大きい文字の数
uint64_t rankMoreThan(uint64_t c, uint64_t begin, uint64_t end) {
auto t = rankAll(c, begin, end);
return std::get<2>(t);
}
// v[begin, end)で(cと同じ値の数、cより小さい値の数、cより大きい値の数)を求める
std::tuple<uint64_t, uint64_t, uint64_t> rankAll(const uint64_t c, uint64_t begin, uint64_t end) {
assert(end <= size);
const uint64_t num = end - begin;
if (begin >= end) {
return std::make_tuple(0, 0, 0);
}
if (c >= maximum_element || end == 0) {
return std::make_tuple(0, num, 0);
}
uint64_t rank_less_than = 0, rank_more_than = 0;
for (size_t i = 0; i < bit_size && begin < end; ++i) {
const uint64_t bit = (c >> (bit_size - i - 1)) & 1;
const uint64_t rank0_begin = this->bit_arrays.at(i).rank(0, begin);
const uint64_t rank0_end = this->bit_arrays.at(i).rank(0, end);
const uint64_t rank1_begin = begin - rank0_begin;
const uint64_t rank1_end = end - rank0_end;
if (bit) {
rank_less_than += (rank0_end - rank0_begin); // i番目のbitが0のものは除外される
begin = this->begin_one.at(i) + rank1_begin;
end = this->begin_one.at(i) + rank1_end;
} else {
rank_more_than += (rank1_end - rank1_begin); // i番目のbitが1のものは除外される
begin = rank0_begin;
end = rank0_end;
}
}
const uint64_t rank = num - rank_less_than - rank_more_than;
return std::make_tuple(rank, rank_less_than, rank_more_than);
}
// T[s, e)で出現回数が多い順にk個の(値，頻度)を返す
// 頻度が同じ場合は値が小さいものが優先される
std::vector<std::pair<uint64_t, uint64_t>> topk(uint64_t s, uint64_t e, uint64_t k) {
assert(s < e);
std::vector<std::pair<uint64_t, uint64_t>> result;
// (頻度，深さ，値)の順でソート
auto c = [](const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &l, const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &r) {
// width
if (std::get<0>(l) != std::get<0>(r)) {
return std::get<0>(l) < std::get<0>(r);
}
// depth
if (std::get<3>(l) != std::get<3>(r)) {
return std::get<3>(l) > std::get<3>(r);
}
// value
if (std::get<4>(l) != std::get<4>(r)) {
return std::get<4>(l) > std::get<4>(r);
}
return true;
};
std::priority_queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>, std::vector<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>>, decltype(c)> que(c); // width, left, right, depth, value
que.push(std::make_tuple(e - s, s, e, 0, 0));
while (not que.empty()) {
auto element = que.top(); que.pop();
uint64_t width, left, right, depth, value;
std::tie(width, left, right, depth, value) = element;
if (depth >= this->bit_size) {
result.emplace_back(std::make_pair(value, right - left));
if (result.size() >= k) {
break;
}
continue;
}
// 0
const uint64_t left0 = this->bit_arrays.at(depth).rank(0, left);
const uint64_t right0 = this->bit_arrays.at(depth).rank(0, right);
if (left0 < right0) {
que.push(std::make_tuple(right0 - left0, left0, right0, depth + 1, value));
}
// 1
const uint64_t left1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, left);
const uint64_t right1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, right);
if (left1 < right1) {
que.push(std::make_tuple(right1 - left1, left1, right1, depth + 1, value | (1 << (bit_size - depth - 1))));
}
}
return result;
};
// T[begin_pos, end_pos)でx <= c < yを満たすcの和を返す
uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t x, const uint64_t y) {
return rangeSum(begin, end, 0, 0, x, y);
}
// T[begin_pos, end_pos)でx <= c < yを満たす最大のcを返す
uint64_t prevValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, uint64_t y) {
assert(end_pos <= size);
const uint64_t num = end_pos - begin_pos;
if (x >= y or y == 0) {
return NOTFOUND;
}
if (y > maximum_element) {
y = maximum_element;
}
if (begin_pos >= end_pos) {
return NOTFOUND;
}
if (x >= maximum_element || end_pos == 0) {
return NOTFOUND;
}
y--; // x <= c <= yにする
std::stack<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, bool>> s; // (begin, end, depth, c, tight)
s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));
while (not s.empty()) {
uint64_t b, e, depth, c;
bool tight;
std::tie(b, e, depth, c, tight) = s.top(); s.pop();
if (depth == bit_size) {
if (c >= x) {
return c;
}
continue;
}
const uint64_t bit = (y >> (bit_size - depth - 1)) & 1;
const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);
const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);
const uint64_t rank1_begin = b - rank0_begin;
const uint64_t rank1_end = e - rank0_end;
// d番目のbitが0のものを使う
const uint64_t b0 = rank0_begin;
const uint64_t e0 = rank0_end;
if (b0 != e0) { // 範囲がつぶれてない
const uint64_t c0 = ((c << 1) | 0);
s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight and bit == 0));
}
// d番目のbitが1のものを使う
const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;
const uint64_t e1 = this->begin_one.at(depth) + rank1_end;
if (b1 != e1) {
if (not tight or bit == 1) {
const auto c1 = ((c << 1) | 1);
s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight));
}
}
}
return NOTFOUND;
}
// T[begin_pos, end_pos)でx <= c < yを満たす最小のcを返す
uint64_t nextValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, const uint64_t y) {
assert(end_pos <= size);
const uint64_t num = end_pos - begin_pos;
if (x >= y or y == 0) {
return NOTFOUND;
}
if (begin_pos >= end_pos) {
return NOTFOUND;
}
if (x >= maximum_element || end_pos == 0) {
return NOTFOUND;
}
std::stack<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, bool>> s; // (begin, end, depth, c, tight)
s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));
while (not s.empty()) {
uint64_t b, e, depth, c;
bool tight;
std::tie(b, e, depth, c, tight) = s.top(); s.pop();
if (depth == bit_size) {
if (c < y) {
return c;
}
continue;
}
const uint64_t bit = (x >> (bit_size - depth - 1)) & 1;
const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);
const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);
const uint64_t rank1_begin = b - rank0_begin;
const uint64_t rank1_end = e - rank0_end;
// d番目のbitが1のものを使う
const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;
const uint64_t e1 = this->begin_one.at(depth) + rank1_end;
if (b1 != e1) {
const auto c1 = ((c << 1) | 1);
s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight and bit == 1));
}
// d番目のbitが0のものを使う
const uint64_t b0 = rank0_begin;
const uint64_t e0 = rank0_end;
if (b0 != e0) {
if (not tight or bit == 0) {
const uint64_t c0 = ((c << 1) | 0);
s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight));
}
}
}
return NOTFOUND;
}
// T[s1, e1)とT[s2, e2)に共通して出現する要素を求める
std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersect(uint64_t _s1, uint64_t _e1, uint64_t _s2, uint64_t _e2) {
assert(_s1 < _e1);
assert(_s2 < _e2);
std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersection;
std::queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>> que; // s1, e1, s2, e2, depth, value
que.push(std::make_tuple(_s1, _e1, _s2, _e2, 0, 0));
while (not que.empty()) {
auto e = que.front(); que.pop();
uint64_t s1, e1, s2, e2, depth, value;
std::tie(s1, e1, s2, e2, depth, value) = e;
if (depth >= this->bit_size) {
intersection.emplace_back(std::make_tuple(value, e1 - s1, e2 - s2));
continue;
}
// 0
uint64_t s1_0 = this->bit_arrays.at(depth).rank(0, s1);
uint64_t e1_0 = this->bit_arrays.at(depth).rank(0, e1);
uint64_t s2_0 = this->bit_arrays.at(depth).rank(0, s2);
uint64_t e2_0 = this->bit_arrays.at(depth).rank(0, e2);
if (s1_0 != e1_0 and s2_0 != e2_0) {
que.push(std::make_tuple(s1_0, e1_0, s2_0, e2_0, depth + 1, value));
}
// 1
uint64_t s1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s1);
uint64_t e1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e1);
uint64_t s2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s2);
uint64_t e2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e2);
if (s1_1 != e1_1 and s2_1 != e2_1) {
que.push(std::make_tuple(s1_1, e1_1, s2_1, e2_1, depth + 1, value | (1 << bit_size - depth - 1)));
}
}
return intersection;
};
private:
uint64_t get_num_of_bit(uint64_t x) {
if (x == 0) return 0;
x--;
uint64_t bit_num = 0;
while (x >> bit_num) {
++bit_num;
}
return bit_num;
}
uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t depth, const uint64_t c, const uint64_t x, const uint64_t y) {
if (begin == end) {
return 0;
}
if (depth == bit_size) {
if (x <= c and c < y) {
return c * (end - begin); // 値 * 頻度
}
return 0;
}
const uint64_t next_c = ((uint64_t)1 << (bit_size - depth - 1)) | c; // 上からdepth番目のbitを立てる
const uint64_t all_one_c = (((uint64_t)1 << (bit_size - depth - 1)) - 1) | next_c; // depth以降のbitをたてる(これ以降全部1を選んだときの値)
if(all_one_c < x or y <= c) {
return 0;
}
// [begin, pos)のすべての要素は[x, y)
if (x <= c and all_one_c < y) {
return this->cumulative_sum.at(depth).at(end) - this->cumulative_sum.at(depth).at(begin);
}
const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, begin);
const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, end);
const uint64_t rank1_begin = begin - rank0_begin;
const uint64_t rank1_end = end - rank0_end;
return rangeSum(rank0_begin, rank0_end, depth + 1, c, x, y) +
rangeSum(this->begin_one.at(depth) + rank1_begin, this->begin_one[depth] + rank1_end, depth + 1, next_c, x, y);
}
};
uint64_t solve(int N, int K, vector<uint64_t> &A) {
WaveletMatrix wm(A);
uint64_t ans = yab;
rep(i, N - K + 1) {
uint64_t begin = i;
uint64_t end = i + K;
uint64_t idx = wm.quantileRange(begin, end, K / 2);
uint64_t m = wm.access(idx);
auto less_sum = wm.rangeSum(begin, end, 0, m);
auto more_sum = wm.rangeSum(begin, end, m, 1000000010);
auto less_freq = wm.rangeFreq(begin, end, 0, m);
auto more_freq = wm.rangeFreq(begin, end, m, 1000000010);
auto a = m * less_freq - less_sum;
auto b = more_sum - m * more_freq;
chmin(ans, a + b);
}
return ans;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, K;
cin >> N >> K;
vector<uint64_t> A(N);
rep(i, N) {
cin >> A[i];
}
cout<<solve(N, K, A) << endl;
}