結果

問題 No.738 平らな農地
コンテスト
ユーザー kazuma
提出日時 2018-09-28 22:28:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 918 ms / 2,000 ms
コード長 5,158 bytes
コンパイル時間 2,157 ms
コンパイル使用メモリ 213,816 KB
最終ジャッジ日時 2025-01-06 13:55:57
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class fid {
	int n;
	vector<bool> data;
	vector<int> ra, se0, se1;
public:
	fid(int n_) : n(n_), data(n), ra(n + 1) {}
	void set(int i) {
		data[i] = true;
	}
	void build() {
		for (int i = 0; i < n; i++) {
			ra[i + 1] = ra[i] + data[i];
		}
		for (int i = 0; i < n; i++) {
			(data[i] ? se1 : se0).push_back(i);
		}
	}
	int rank(int i, bool b) const {
		return b ? ra[i] : i - ra[i];
	}
	int rank(int l, int r, bool b) const {
		return rank(r, b) - rank(l, b);
	}
	int select(int x, bool b) const {
		return (b ? se1 : se0)[x];
	}
	int select(int l, int x, bool b) const {
		return select(x + rank(l, b), b);
	}
};

template <typename T>
class wavelet_matrix {
	T h;
	int n;
	vector<fid> data;
	vector<int> mid;

	T get_h(T val) {
		T res = 1;
		while ((1LL << res) <= val) ++res;
		return res;
	}
public:
	wavelet_matrix(const vector<T>& data_)
		: h(get_h(*max_element(data_.begin(), data_.end()))), n(data_.size()), mid(h) {
		data.assign(h, n);
		vector<T> ar1(data_), ar2(n);
		for (T b = 0; b < h; b++) {
			int p = 0;
			for (int i = 0; i < n; i++) {
				if ((ar1[i] & ((T)1 << (h - 1 - b))) == 0) {
					ar2[p++] = ar1[i];
				}
			}
			mid[b] = p;
			for (int i = 0; i < n; i++) {
				if (ar1[i] & ((T)1 << (h - 1 - b))) {
					data[b].set(i);
					ar2[p++] = ar1[i];
				}
			}
			data[b].build();
			ar1.swap(ar2);
		}
	}
	int rank(int p, T val) {
		return rank(0, p, val);
	}
	int rank(int l, int r, T val) {
		if (val >> h) return 0;
		for (T b = 0; b < h; b++) {
			if (val & ((T)1 << (h - 1 - b))) {
				l = data[b].rank(l, true) + mid[b];
				r = data[b].rank(r, true) + mid[b];
			}
			else {
				l = data[b].rank(l, false);
				r = data[b].rank(r, false);
			}
		}
		return r - l;
	}
	int rank_less_than(int l, int r, T ub) {
		if (ub >> h) return r - l;
		int res = 0;
		for (T b = 0; b < h; b++) {
			bool d = (ub >> (h - 1 - b)) & 1;
			int lcnt = data[b].rank(l, d);
			int rcnt = data[b].rank(r, d);
			if (d) res += (r - l) - (rcnt - lcnt);
			l = lcnt;
			r = rcnt;
			if (d) {
				l += mid[b];
				r += mid[b];
			}
		}
		return res;
	}
	int rank_range(int l, int r, T lb, T ub) {
		return rank_less_than(l, r, ub) - rank_less_than(l, r, lb);
	}
	int select(int x, T val) {
		static int left[h];
		int l = 0, r = n;
		for (T b = 0; b < h; b++) {
			left[b] = l;
			if (val & ((T)1 << (h - 1 - b))) {
				l = data[b].rank(l, true) + mid[b];
				r = data[b].rank(r, true) + mid[b];
			}
			else {
				l = data[b].rank(l, false);
				r = data[b].rank(r, false);
			}
		}
		for (int b = h - 1; b >= 0; b--) {
			x = data[b].select(left[b], x, (bool)((val >> (h - 1 - b)) & 1)) - left[b];
		}
		return x;
	}
	int select(int l, int r, int x, T val) {
		return select(x + rank(l, val), val);
	}
	T kth_element(int l, int r, int k) {
		T res = 0;
		for (T b = 0; b < h; b++) {
			int cnt = data[b].rank(l, r, false);
			res <<= 1;
			if (k >= cnt) {
				l = data[b].rank(l, true) + mid[b];
				r = data[b].rank(r, true) + mid[b];
				k -= cnt;
				res |= 1;
			}
			else {
				l = data[b].rank(l, false);
				r = data[b].rank(r, false);
			}
		}
		return res;
	}
};

template <typename T>
class merge_tree {
	const int n;
	vector<vector<T>> data, sum;
	int size(int x) {
		int res = 1;
		while (res < x) res <<= 1;
		return res;
	}
	T query1(int node, T val) {
		int ub = lower_bound(data[node].begin(), data[node].end(), val) - data[node].begin();
		return sum[node][ub] - sum[node][0];
	}
	T query2(int node, T val) {
		int ub = lower_bound(data[node].begin(), data[node].end(), val) - data[node].begin();
		return sum[node].back() - sum[node][ub];
	}
public:
	merge_tree(const vector<T>& data_) : n(size(data_.size())), data(n * 2), sum(n * 2) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n].push_back(data_[i]);
		for (int i = n - 1; i >= 0; i--)
			merge(data[i * 2].begin(), data[i * 2].end(), data[i * 2 + 1].begin(), data[i * 2 + 1].end(), back_inserter(data[i]));
		for (int i = 0; i < n * 2; i++) {
			sum[i].assign(data[i].size() + 1, 0);
			for (int j = 0; j < (int)data[i].size(); j++) {
				sum[i][j + 1] = sum[i][j] + data[i][j];
			}
		}
	}
	T find1(int l, int r, T val) {
		l += n; r += n;
		T res = 0;
		while (l < r) {
			if (l & 1) res += query1(l++, val);
			if (r & 1) res += query1(--r, val);
			l >>= 1; r >>= 1;
		}
		return res;
	}
	T find2(int l, int r, T val) {
		l += n; r += n;
		T res = 0;
		while (l < r) {
			if (l & 1) res += query2(l++, val);
			if (r & 1) res += query2(--r, val);
			l >>= 1; r >>= 1;
		}
		return res;
	}
};

int main()
{
	int N, K;
	cin >> N >> K;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	wavelet_matrix<ll> wm(A);
	merge_tree<ll> mt(A);
	ll res = LLONG_MAX;
	for (int i = 0; i + K <= N; i++) {
		ll lb = 1, ub = 1e9 + 1;
		while (ub - lb > 1) {
			ll c = (lb + ub) >> 1;
			if (wm.rank_less_than(i, i + K, c) < (K + 1) / 2) {
				lb = c;
			}
			else {
				ub = c;
			}
		}
		res = min(res, (wm.rank_less_than(i, i + K, lb) * lb - mt.find1(i, i + K, lb)) + (mt.find2(i, i + K, lb) - (ll)(K - wm.rank_less_than(i, i + K, lb)) * lb));
	}
	cout << res << endl;
	return 0;
}
0