#288029 (C++17) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	kazuma
提出日時	2018-09-28 22:28:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,357 ms / 2,000 ms
コード長	5,158 bytes
コンパイル時間	2,705 ms
コンパイル使用メモリ	222,304 KB
実行使用メモリ	80,248 KB
最終ジャッジ日時	2024-10-12 06:51:38
合計ジャッジ時間	41,155 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	16 ms 5,376 KB
testcase_06	AC	18 ms 5,376 KB
testcase_07	AC	14 ms 5,504 KB
testcase_08	AC	8 ms 5,248 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	3 ms 5,248 KB
testcase_11	AC	8 ms 5,248 KB
testcase_12	AC	4 ms 5,248 KB
testcase_13	AC	15 ms 5,248 KB
testcase_14	AC	6 ms 5,248 KB
testcase_15	AC	522 ms 75,092 KB
testcase_16	AC	532 ms 75,784 KB
testcase_17	AC	643 ms 75,636 KB
testcase_18	AC	620 ms 74,684 KB
testcase_19	AC	743 ms 78,860 KB
testcase_20	AC	544 ms 75,996 KB
testcase_21	AC	707 ms 79,176 KB
testcase_22	AC	568 ms 76,180 KB
testcase_23	AC	701 ms 77,220 KB
testcase_24	AC	711 ms 76,476 KB
testcase_25	AC	5 ms 5,248 KB
testcase_26	AC	6 ms 5,248 KB
testcase_27	AC	6 ms 5,248 KB
testcase_28	AC	5 ms 5,248 KB
testcase_29	AC	6 ms 5,248 KB
testcase_30	AC	5 ms 5,248 KB
testcase_31	AC	5 ms 5,248 KB
testcase_32	AC	5 ms 5,248 KB
testcase_33	AC	6 ms 5,248 KB
testcase_34	AC	5 ms 5,248 KB
testcase_35	AC	5 ms 5,248 KB
testcase_36	AC	5 ms 5,248 KB
testcase_37	AC	5 ms 5,248 KB
testcase_38	AC	5 ms 5,248 KB
testcase_39	AC	5 ms 5,248 KB
testcase_40	AC	5 ms 5,248 KB
testcase_41	AC	6 ms 5,248 KB
testcase_42	AC	5 ms 5,248 KB
testcase_43	AC	5 ms 5,248 KB
testcase_44	AC	5 ms 5,248 KB
testcase_45	AC	493 ms 80,076 KB
testcase_46	AC	507 ms 75,256 KB
testcase_47	AC	493 ms 78,196 KB
testcase_48	AC	427 ms 76,412 KB
testcase_49	AC	426 ms 75,652 KB
testcase_50	AC	421 ms 77,948 KB
testcase_51	AC	533 ms 78,656 KB
testcase_52	AC	473 ms 75,796 KB
testcase_53	AC	489 ms 76,776 KB
testcase_54	AC	516 ms 78,640 KB
testcase_55	AC	546 ms 78,452 KB
testcase_56	AC	527 ms 77,744 KB
testcase_57	AC	476 ms 74,760 KB
testcase_58	AC	483 ms 77,364 KB
testcase_59	AC	471 ms 80,004 KB
testcase_60	AC	448 ms 79,456 KB
testcase_61	AC	463 ms 79,056 KB
testcase_62	AC	454 ms 75,136 KB
testcase_63	AC	543 ms 79,968 KB
testcase_64	AC	506 ms 78,968 KB
testcase_65	AC	853 ms 75,872 KB
testcase_66	AC	961 ms 77,860 KB
testcase_67	AC	688 ms 74,712 KB
testcase_68	AC	659 ms 76,436 KB
testcase_69	AC	1,091 ms 77,412 KB
testcase_70	AC	868 ms 79,368 KB
testcase_71	AC	150 ms 55,892 KB
testcase_72	AC	619 ms 74,456 KB
testcase_73	AC	424 ms 73,636 KB
testcase_74	AC	797 ms 77,168 KB
testcase_75	AC	1,010 ms 74,852 KB
testcase_76	AC	751 ms 76,552 KB
testcase_77	AC	1,357 ms 74,644 KB
testcase_78	AC	1,312 ms 78,976 KB
testcase_79	AC	1,188 ms 79,564 KB
testcase_80	AC	783 ms 77,184 KB
testcase_81	AC	950 ms 75,524 KB
testcase_82	AC	919 ms 77,688 KB
testcase_83	AC	734 ms 80,248 KB
testcase_84	AC	649 ms 78,716 KB
testcase_85	AC	1,088 ms 79,408 KB
testcase_86	AC	1,026 ms 74,644 KB
testcase_87	AC	174 ms 77,292 KB
testcase_88	AC	166 ms 74,800 KB
testcase_89	AC	2 ms 5,248 KB
testcase_90	AC	2 ms 5,248 KB
testcase_91	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード