結果

問題 No.738 平らな農地
ユーザー kazumakazuma
提出日時 2018-09-28 22:28:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 985 ms / 2,000 ms
コード長 5,158 bytes
コンパイル時間 2,468 ms
コンパイル使用メモリ 217,760 KB
実行使用メモリ 80,232 KB
最終ジャッジ日時 2024-04-20 11:12:28
合計ジャッジ時間 35,445 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 15 ms
6,940 KB
testcase_06 AC 17 ms
6,944 KB
testcase_07 AC 13 ms
6,944 KB
testcase_08 AC 7 ms
6,940 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 7 ms
6,944 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 13 ms
6,944 KB
testcase_14 AC 6 ms
6,940 KB
testcase_15 AC 483 ms
75,112 KB
testcase_16 AC 495 ms
76,152 KB
testcase_17 AC 596 ms
75,720 KB
testcase_18 AC 572 ms
74,588 KB
testcase_19 AC 690 ms
78,936 KB
testcase_20 AC 506 ms
76,172 KB
testcase_21 AC 665 ms
79,012 KB
testcase_22 AC 530 ms
76,404 KB
testcase_23 AC 642 ms
77,308 KB
testcase_24 AC 652 ms
76,524 KB
testcase_25 AC 5 ms
6,944 KB
testcase_26 AC 4 ms
6,940 KB
testcase_27 AC 4 ms
6,940 KB
testcase_28 AC 5 ms
6,940 KB
testcase_29 AC 5 ms
6,940 KB
testcase_30 AC 4 ms
6,944 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 4 ms
6,944 KB
testcase_33 AC 6 ms
6,940 KB
testcase_34 AC 5 ms
6,940 KB
testcase_35 AC 4 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,940 KB
testcase_39 AC 4 ms
6,944 KB
testcase_40 AC 5 ms
6,944 KB
testcase_41 AC 5 ms
6,940 KB
testcase_42 AC 4 ms
6,940 KB
testcase_43 AC 4 ms
6,944 KB
testcase_44 AC 4 ms
6,944 KB
testcase_45 AC 443 ms
79,952 KB
testcase_46 AC 455 ms
75,176 KB
testcase_47 AC 457 ms
78,276 KB
testcase_48 AC 394 ms
76,308 KB
testcase_49 AC 391 ms
75,748 KB
testcase_50 AC 383 ms
77,920 KB
testcase_51 AC 491 ms
78,748 KB
testcase_52 AC 434 ms
75,740 KB
testcase_53 AC 449 ms
76,912 KB
testcase_54 AC 482 ms
78,692 KB
testcase_55 AC 499 ms
78,452 KB
testcase_56 AC 471 ms
77,800 KB
testcase_57 AC 439 ms
75,096 KB
testcase_58 AC 438 ms
77,448 KB
testcase_59 AC 431 ms
80,044 KB
testcase_60 AC 404 ms
79,420 KB
testcase_61 AC 429 ms
78,932 KB
testcase_62 AC 417 ms
75,204 KB
testcase_63 AC 506 ms
79,924 KB
testcase_64 AC 459 ms
78,956 KB
testcase_65 AC 756 ms
76,092 KB
testcase_66 AC 792 ms
77,764 KB
testcase_67 AC 536 ms
74,796 KB
testcase_68 AC 535 ms
76,400 KB
testcase_69 AC 865 ms
77,620 KB
testcase_70 AC 668 ms
79,316 KB
testcase_71 AC 134 ms
55,700 KB
testcase_72 AC 602 ms
74,708 KB
testcase_73 AC 392 ms
73,788 KB
testcase_74 AC 744 ms
77,260 KB
testcase_75 AC 782 ms
74,880 KB
testcase_76 AC 599 ms
76,724 KB
testcase_77 AC 863 ms
74,568 KB
testcase_78 AC 946 ms
78,984 KB
testcase_79 AC 985 ms
79,368 KB
testcase_80 AC 683 ms
77,420 KB
testcase_81 AC 802 ms
75,296 KB
testcase_82 AC 797 ms
77,648 KB
testcase_83 AC 687 ms
80,232 KB
testcase_84 AC 603 ms
78,476 KB
testcase_85 AC 907 ms
79,432 KB
testcase_86 AC 841 ms
74,660 KB
testcase_87 AC 157 ms
77,160 KB
testcase_88 AC 147 ms
74,936 KB
testcase_89 AC 2 ms
6,944 KB
testcase_90 AC 2 ms
6,944 KB
testcase_91 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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