#176487 (C++14) No.738 平らな農地

• 問題: No.738 平らな農地
• ユーザー: しらっ亭
• 提出日時: 2017-06-01 20:29:08
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 146 ms / 2,000 ms
• コード長: 3,802 bytes
• コンパイル時間: 2,027 ms
• コンパイル使用メモリ: 183,588 KB
• 実行使用メモリ: 9,856 KB
• 最終ジャッジ日時: 2024-10-13 13:43:32
• 合計ジャッジ時間: 9,730 ms
• ジャッジサーバーID （参考情報）: judge3 / 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	3 ms; 5,248 KB
testcase_06	AC	4 ms; 5,248 KB
testcase_07	AC	5 ms; 5,248 KB
testcase_08	AC	3 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	4 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	130 ms; 9,112 KB
testcase_16	AC	131 ms; 9,344 KB
testcase_17	AC	132 ms; 9,472 KB
testcase_18	AC	129 ms; 9,088 KB
testcase_19	AC	103 ms; 9,728 KB
testcase_20	AC	138 ms; 9,216 KB
testcase_21	AC	140 ms; 9,728 KB
testcase_22	AC	143 ms; 9,472 KB
testcase_23	AC	128 ms; 9,600 KB
testcase_24	AC	116 ms; 9,344 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	3 ms; 5,248 KB
testcase_27	AC	3 ms; 5,248 KB
testcase_28	AC	3 ms; 5,248 KB
testcase_29	AC	3 ms; 5,248 KB
testcase_30	AC	3 ms; 5,248 KB
testcase_31	AC	2 ms; 5,248 KB
testcase_32	AC	2 ms; 5,248 KB
testcase_33	AC	2 ms; 5,248 KB
testcase_34	AC	2 ms; 5,248 KB
testcase_35	AC	2 ms; 5,248 KB
testcase_36	AC	2 ms; 5,248 KB
testcase_37	AC	2 ms; 5,248 KB
testcase_38	AC	2 ms; 5,248 KB
testcase_39	AC	3 ms; 5,248 KB
testcase_40	AC	3 ms; 5,248 KB
testcase_41	AC	2 ms; 5,248 KB
testcase_42	AC	2 ms; 5,248 KB
testcase_43	AC	3 ms; 5,248 KB
testcase_44	AC	2 ms; 5,248 KB
testcase_45	AC	134 ms; 9,728 KB
testcase_46	AC	128 ms; 9,228 KB
testcase_47	AC	136 ms; 9,600 KB
testcase_48	AC	121 ms; 9,344 KB
testcase_49	AC	122 ms; 9,344 KB
testcase_50	AC	125 ms; 9,600 KB
testcase_51	AC	139 ms; 9,728 KB
testcase_52	AC	129 ms; 9,344 KB
testcase_53	AC	134 ms; 9,344 KB
testcase_54	AC	140 ms; 9,600 KB
testcase_55	AC	137 ms; 9,728 KB
testcase_56	AC	146 ms; 9,600 KB
testcase_57	AC	128 ms; 9,088 KB
testcase_58	AC	133 ms; 9,600 KB
testcase_59	AC	143 ms; 9,728 KB
testcase_60	AC	134 ms; 9,856 KB
testcase_61	AC	128 ms; 9,600 KB
testcase_62	AC	137 ms; 9,240 KB
testcase_63	AC	142 ms; 9,728 KB
testcase_64	AC	135 ms; 9,728 KB
testcase_65	AC	11 ms; 5,248 KB
testcase_66	AC	11 ms; 5,248 KB
testcase_67	AC	51 ms; 9,216 KB
testcase_68	AC	50 ms; 9,472 KB
testcase_69	AC	65 ms; 9,600 KB
testcase_70	AC	60 ms; 9,728 KB
testcase_71	AC	46 ms; 9,728 KB
testcase_72	AC	58 ms; 9,216 KB
testcase_73	AC	63 ms; 9,472 KB
testcase_74	AC	54 ms; 9,600 KB
testcase_75	AC	62 ms; 9,216 KB
testcase_76	AC	63 ms; 9,472 KB
testcase_77	AC	57 ms; 9,216 KB
testcase_78	AC	63 ms; 9,600 KB
testcase_79	AC	86 ms; 9,728 KB
testcase_80	AC	77 ms; 9,600 KB
testcase_81	AC	74 ms; 9,216 KB
testcase_82	AC	74 ms; 9,600 KB
testcase_83	AC	79 ms; 9,856 KB
testcase_84	AC	87 ms; 9,600 KB
testcase_85	AC	25 ms; 9,728 KB
testcase_86	AC	25 ms; 9,216 KB
testcase_87	AC	86 ms; 9,472 KB
testcase_88	AC	79 ms; 9,216 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

ソースコード

// verify のために http://yukicoder.me/submissions/131359 から treap を借りて、sum 機能を追加しました
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool lsss(int x,int y);

struct Treap{
private:
	static const ll rd_msk = (1ll<<32)-1;
	static ll rd(){
		static ll rd_x = 123456789;
		static ll rd_y = 362436069;
		static ll rd_z = 521288629;
		static ll rd_w = 88675123;
		ll t = (rd_x^(rd_x<<11))&rd_msk;
		rd_x = rd_y;
		rd_y = rd_z;
		rd_z = rd_w;
		return rd_w = (rd_w^(rd_w>>19)) ^ (t^(t>>8));
	}
	struct node{
		ll val,pri,cnt, sum;
		node *lch, *rch;
		node(ll val):val(val),cnt(1),sum(val){
			pri = rd();
			lch = rch = NULL;
		}
	};
public:
	node *root;
	Treap():root(NULL){}
private:
	ll count(node *t){return t==NULL?0:t->cnt;}
	ll sum(node *t){return t==NULL?0:t->sum;}
	node* update(node *t){
		t->cnt=count(t->lch)+count(t->rch)+1;
		t->sum=sum(t->lch)+sum(t->rch)+t->val;
		return t;
	}
	node* merge(node *l, node *r){
		if(!l || !r)return !l?r:l;
		if(l->pri > r->pri){
			l->rch = merge(l->rch,r);
			return update(l);
		}else{
			r->lch = merge(l,r->lch);
			return update(r);
		}
	}
	pair<node*,node*> split(node *t, ll k){
		if(!t) return make_pair<node*,node*>(NULL,NULL);
		if(k <= count(t->lch)){
			pair<node*,node*> s = split(t->lch,k);
			t->lch = s.second;
			return make_pair(s.first,update(t));
		}else{
			pair<node*,node*> s = split(t->rch,k-count(t->lch)-1);
			t->rch = s.first;
			return make_pair(update(t),s.second);
		}
	}
	ll __find(node *p,ll v){
		if(!p)return 0;
		if(p->val==v)return count(p->lch);
		return (lsss(v,p->val))?__find(p->lch,v):(count(p->lch)+1+__find(p->rch,v));
	}
	ll __lsss(node *p,ll v){
		if(!p)return 0;
		return (!lsss(p->val,v))?__lsss(p->lch,v):(count(p->lch)+1+__lsss(p->rch,v));
	}
	ll __lsss_eq(node *p,ll v){
		if(!p)return 0;
		return (lsss(v,p->val))?__lsss_eq(p->lch,v):(count(p->lch)+1+__lsss_eq(p->rch,v));
	}
	ll __get_at(node *p,ll k,ll acc){
		if(!p)return -1;
		ll lc=count(p->lch);
		if(acc+lc==k)return p->val;
		if(acc+lc>k)return __get_at(p->lch,k,acc);
		if(acc+lc<k)return __get_at(p->rch,k,acc+lc+1);
		assert(false);
	}
public:
	void merge(Treap that){
		root = merge(root, that.root);
	}
	Treap split(ll k){
		Treap that;
		pair<node*,node*> p = split(root,k);
		root = p.first;
		that.root = p.second;
		return that;
	}
	void insert_at(ll v,ll k){
		pair<node*,node*> p = split(root,k);
		node* nn = new node(v);
		root = merge(p.first, nn);
		root = merge(root, p.second);
	}
	void erase_at(ll k){
		pair<node*,node*> p,q;
		q = split(root,k+1);
		p = split(q.first,k);
		root = merge(p.first, q.second);
	}
	void insert_by(ll v){
		insert_at(v,__lsss(root,v));
	}
	void erase_by(ll v){
		erase_at(__find(root,v));
	}
	ll count_lsss(ll v){
		return __lsss(root,v);
	}
	ll count_lsss_equal(ll v){
		return __lsss_eq(root,v);
	}
	ll get_at(ll k){
		return __get_at(root,k,0);
	}
	ll size(){
		return count(root);
	}
};

bool lsss(int x,int y){
	return x < y;
}

int64_t solve(const int n, const int k, const vector<int> &A) {
	if (k == 1) return 0;

	int l = (k + 1) / 2;
	int m = k - l;
	Treap treap;

	ll ans = 1e18;

	for (int i = 0; i < n; i++) {
		treap.insert_by(A[i]);

		if (i >= k) treap.erase_by(A[i-k]);

		if (i >= k - 1) {
			ll median = treap.get_at(l-1);
			Treap rig = treap.split(l);
			ll sum_of_lower = treap.root->sum;
			ll sum_of_higher = rig.root->sum;
			treap.merge(rig);
			ll inc_cost = median * l - sum_of_lower;
			ll dec_cost = sum_of_higher - median * m;
			ll cand = inc_cost + dec_cost;

			ans = min(ans, cand);
		}
	}

	return ans;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, k; cin >> n >> k;
	vector<int> A(n);
	for (int i = 0; i < n; i++) cin >> A[i];

	cout << solve(n, k, A) << endl;

	return 0;
}