結果
問題 | No.738 平らな農地 |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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, 交差dのn個の数列の和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; // 各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;}// 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);// 0をtempにいれてくfor (uint64_t j = 0; j < v.size(); ++j) {uint64_t c = v[j];uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbitif (bit == 0) {temp.push_back(c);// bit_arrays[i].setBit(0, j);b[j] = 0;}}this->begin_one[i] = temp.size();// 1をtempにいれてくfor (uint64_t j = 0; j < v.size(); ++j) {uint64_t c = v[j];uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbitif (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)で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[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; // 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[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; // 上からi番目のbit// left = bit_arrays[i).rank(bit, left); // cのi番目のbitと同じ数値の数// 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; // 上からi番目のbitpos = bit_arrays[i].rank(bit, pos); // cのi番目のbitと同じ数値の数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)で(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[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); // i番目のbitが0のものは除外されるbegin = this->begin_one[i] + rank1_begin;end = this->begin_one[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[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);}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) { // 1の数にkが収まっていればl = lc+begin_one[d], r = rc+begin_one[d]; // 1側に遷移ret |= 1ULL<<(bit_size-d-1);} else { // 0側ならばk -= rc-lc; // 1側にあった数だけkを削って次へ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; // 上から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[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));}