Submission

Score: 76

User: qweqwe

Problemset: แคง (Kang)

Language: cpp

Time: 2.085 second

Submitted On: 2026-03-26 21:37:25

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

multiset<pii> small,big;
unordered_map<ll,ll> cnt;
ll sum_big=0,sum=0;

void balance(int k){
	while (big.size() < k && !small.empty()){
		auto it_s=--small.end();
		sum_big += it_s->first;
		small.erase(it_s);
		big.insert(*it_s);
	}
	while (big.size() > k){
		auto it_b=big.begin();
		sum_big -= it_b->first;
		big.erase(it_b);
		small.insert(*it_b);
	}
	while (!small.empty() && !big.empty()){
		auto it_s=--small.end();
		auto it_b=big.begin();
		if (it_s->first > it_b->first){
			sum_big += llabs(it_s->first-it_b->first);
			
			pii s=*it_s;
			pii b=*it_b;
			
			small.erase(it_s);
			big.erase(it_b);
			
			small.insert(b);
			big.insert(s);
		}else break;
	}
}

void add_contri(ll val,ll f){
	ll temp=val*f;
	small.insert({temp,val});
}

void erase_contri(ll val,ll f){
	ll temp=val*f;
	pii rem={temp,val};
	auto it=small.find(rem);
	
	if (it==small.end()){
		it=big.find(rem);
		sum_big-=temp;
		big.erase(it);
	}else small.erase(it);
}

void add(ll val){
	if (cnt[val]){
		erase_contri(val,cnt[val]);
	}cnt[val]++;
	add_contri(val,cnt[val]);
	sum+=val;
}

vector<long long> capsize(vector<int> a, vector<int> b) {
	int n=a.size(),m=b.size();
	vector<ll> ans;
	
	for (ll i:a){
		add(i);
	}
	for (int i=0;i<m;i++){
		ll x=b[i];
		add(x);
		balance(i+1);
		ans.push_back(sum-sum_big);
	}
	return ans;
}
/*
5 4
6 3 9 6 3
4 6 9 6

19 10 4 0

8 7
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15

36 36 36 36 36 36 36

5 4
32 78 4 10 9
52 46 33 77

107 101 88 88

5 4
1 2 3 4 5
4 4 4 4
*/