結果

問題 No.738 平らな農地
ユーザー MitI_7
提出日時 2019-02-08 21:32:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 437 ms / 2,000 ms
コード長 15,684 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 202,628 KB
実行使用メモリ 35,916 KB
最終ジャッジ日時 2024-06-28 18:31:57
合計ジャッジ時間 21,774 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x) cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_ON(bit, i) (bit & (1LL << i))
#define BIT_COUNT(bit) (__builtin_popcount(bit))
typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> using VVVV = std::vector<std::vector<std::vector<std::vector<T>>>>;
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) { if (i != 0) {std::cout << " ";} std::cout <<
    v[i];} std::cout << "\n"; }
template<class T> inline void print_2vec(const std::vector<std::vector<T>> &v) { for (int i = 0; i < v.size(); ++i) { for (int j = 0; j < v[0].size
    (); ++j) { if (j != 0) { std::cout << " "; } std::cout << std::setw(13) << std::left << v[i][j]; } std::cout << "\n";}}
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<typename T> T &chmin(T &a, const T &b) { if (b < a) { a = b; } return a; }
template<typename T> T &chmax(T &a, const T &b) { if (b > a) { a = b; } return a; }
template<class T> inline std::vector<T> unique(std::vector<T> v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v;
    }
// s, dn
long long sum_of_arithmetic_progression(long long s, long long d, long long n) { return n * (2 * s + (n - 1) * d) / 2; }
const int INF = 1 << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = {0, -1, 0, 1}, dx4 = {1, 0, -1, 0};
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };
using namespace std;
enum {
NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU
};
class SuccinctBitVector {
public:
vector<uint32_t> bit;
vector<int> acc;
int N;
SuccinctBitVector(vector<int> bit_) {
N = bit_.size();
int N2 = (N >> 5) + 1;
bit.resize(N2);
for(int i = 0; i < N2; i++) {
for(int j = 0; j < 32; j++) {
if ((i << 5) + j < N) bit[i] |= bit_[(i << 5) + j] << j;
}
}
acc = vector<int>(N2);
for(int i = 0; i < N2 - 1; i++) {
acc[i + 1] = acc[i] + __builtin_popcount(bit[i]);
}
}
int rank(int x, int k) {
int n1 = acc[k >> 5] + __builtin_popcount(bit[k >> 5] & (uint32_t)(((1ULL << (k & 0x1f)) - 1)));
return x ? n1 : k - n1;
}
int operator[](int k) {
return ((bit[k >> 5] >> (k & 0x1f)) & 1);
}
size_t size() {
return N;
}
};
class WaveletMatrix {
private:
std::vector<SuccinctBitVector> bit_arrays;
std::vector<uint64_t> begin_one; // bit1
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;
}
// bit_arrays.resize(bit_size);
// 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[0][j + 1] = this->cumulative_sum[0][j] + array[j];
}
std::vector<uint64_t> v(array);
for (uint64_t i = 0; i < bit_size; ++i) {
std::vector<uint64_t> temp;
vector<int> b(v.size(), 0);
// 0temp
for (uint64_t j = 0; j < v.size(); ++j) {
uint64_t c = v[j];
uint64_t bit = (c >> (bit_size - i - 1)) & 1; // ibit
if (bit == 0) {
temp.push_back(c);
// bit_arrays[i].setBit(0, j);
b[j] = 0;
}
}
this->begin_one[i] = temp.size();
// 1temp
for (uint64_t j = 0; j < v.size(); ++j) {
uint64_t c = v[j];
uint64_t bit = (c >> (bit_size - i - 1)) & 1; // ibit
if (bit == 1) {
temp.push_back(c);
// bit_arrays[i].setBit(1, j);
b[j] = 1;
}
}
for (uint64_t j = 0; j < temp.size(); ++j) {
this->cumulative_sum[i + 1][j + 1] = this->cumulative_sum[i + 1][j] + temp[j];
}
// bit_arrays[i].build();
assert(b.size() > 0);
SuccinctBitVector bv(b);
bit_arrays.emplace_back(bv);
v = temp;
}
//
for (int i = v.size() - 1; i >= 0; --i) {
this->begin_alphabet[v[i]] = i;
}
}
// v[begin_pos, end_pos)kindex(k0-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[i].rank(0, begin_pos);
const uint64_t num_of_zero_end = bit_arrays[i].rank(0, end_pos);
const uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin; // beginend0
const uint64_t bit = (k < num_of_zero) ? 0 : 1; // kibit01
if (bit) {
k -= num_of_zero;
begin_pos = this->begin_one[i] + begin_pos - num_of_zero_begin;
end_pos = this->begin_one[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);
}
return val;
// uint64_t left = 0;
// for (uint64_t i = 0; i < bit_size; ++i) {
// const uint64_t bit = (val >> (bit_size - i - 1)) & 1; // ibit
// left = bit_arrays[i).rank(bit, left); // cibit
// if (bit) {
// left += this->begin_one[i);
// }
// }
//
// const uint64_t rank = begin_pos + k - left + 1;
// return select(val, rank) - 1;
}
// 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; // ibit
pos = bit_arrays[i].rank(bit, pos); // cibit
if (bit) {
pos += this->begin_one[i];
}
}
uint64_t begin_pos = this->begin_alphabet[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)(ccc)
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[i].rank(0, begin);
const uint64_t rank0_end = this->bit_arrays[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); // ibit0
begin = this->begin_one[i] + rank1_begin;
end = this->begin_one[i] + rank1_end;
} else {
rank_more_than += (rank1_end - rank1_begin); // ibit1
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[begin_pos, end_pos)x <= c < yc
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);
}
uint64_t freq(uint64_t l, uint64_t r, uint64_t a, uint64_t b) {
return freq_dfs(0, l, r, 0, a, b);
}
// number of elements in [l,r) in [a,b)
// O(log m)
int freq_dfs(uint64_t d, uint64_t l, uint64_t r, uint64_t val, uint64_t a, uint64_t b) {
if(l == r) return 0;
if(d == bit_size) return (a <= val and val < b)? r-l: 0;
uint64_t nv = 1ULL<<(bit_size-d-1)|val, nnv = ((1ULL<<(bit_size-d-1))-1)|nv;
if(nnv < a or b <= val) return 0;
if(a <= val and nnv < b) return r-l;
uint64_t lc = this->bit_arrays[d].rank(1,l);
uint64_t rc = this->bit_arrays[d].rank(1,r);
return freq_dfs(d+1,l-lc,r-rc,val,a,b)+
freq_dfs(d+1,lc+this->begin_one[d],rc+this->begin_one[d],nv,a,b);
}
uint64_t kth_number(uint64_t l, uint64_t r, uint64_t k) {
if(r-l <= k or k < 0) return -1;
uint64_t ret = 0;
for (int d = 0; d < bit_size; d++) {
uint64_t lc = bit_arrays[d].rank(1,l);
uint64_t rc = bit_arrays[d].rank(1,r);
// lc - rc = [l, r)1
if(rc-lc > k) { // 1k
l = lc+begin_one[d], r = rc+begin_one[d]; // 1
ret |= 1ULL<<(bit_size-d-1);
} else { // 0
k -= rc-lc; // 1k
l -= lc, r -= rc;
}
}
return ret;
}
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; // depthbit
const uint64_t all_one_c = (((uint64_t)1 << (bit_size - depth - 1)) - 1) | next_c; // depthbit
            (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[depth][end] - this->cumulative_sum[depth][begin];
}
const uint64_t rank0_begin = this->bit_arrays[depth].rank(0, begin);
const uint64_t rank0_end = this->bit_arrays[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[depth] + rank1_begin, this->begin_one[depth] + rank1_end, depth + 1, next_c, x, y);
}
};
uint64_t solve(int N, int K, V<uint64_t> &A) {
WaveletMatrix wm(A);
uint64_t ans = LONG_LONG_MAX;
FOR(i, 0, N - K + 1) {
uint64_t begin = i;
uint64_t end = i + K;
// uint64_t m = wm.quantileRange(begin, end, K / 2);
uint64_t m = wm.kth_number(begin, end, K / 2);
auto less_sum = wm.rangeSum(begin, end, 0, m);
auto more_sum = wm.rangeSum(begin, end, m, 1000000010);
auto less_freq = wm.freq(begin, end, 0, m);
auto more_freq = wm.freq(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;
V<uint64_t> A(N);
FOR(i, 0, N) {
cin >> A[i];
}
print(solve(N, K, A));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0