結果

問題 No.738 平らな農地
ユーザー しらっ亭
提出日時 2017-06-01 20:29:08
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
}
0