Submission

Score: 100

User: nozmid

Problemset: แคง (Kang)

Language: cpp

Time: 1.048 second

Submitted On: 2026-04-26 00:47:19

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define emb emplace_back
#define em emplace

struct stc{
	ll sum, k, v;
	bool operator<(const stc &o) const{
		if(sum != o.sum) return sum > o.sum;
		return k < o.k;
	}
};

const int maxn = 2e6 + 5;

int n, m;
vector<ll> res;
int mp[maxn];
int re[maxn];
vector<int> vec;
priority_queue<stc> pq;
int sz;
ll ores;

vector<long long> capsize(vector<int> a, vector<int> b){
	n = a.size(), m = b.size();
	res.resize(m);
	for(auto e : a) vec.emb(e);
	for(auto e : b) vec.emb(e);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for(auto e : a){
		int lb = lower_bound(vec.begin(), vec.end(), e) - vec.begin();
		re[lb] = e;
		++mp[lb];
	}
	for(auto &e : b){
		int lb = lower_bound(vec.begin(), vec.end(), e) - vec.begin();
		re[lb] = e;
		++mp[lb];
		e = lb;
	}
	for(int i=0;i<vec.size();++i) pq.em(stc{1LL*re[i]*mp[i], i, mp[i]});
	while(pq.size() > m){
		stc it = pq.top();
		mp[it.k] = 0;
		res[m-1] += (it.sum);
		pq.pop();
	}
	ores = res[m-1];
	sz = pq.size();
	for(int i=m-2;i>=0;--i){
		ll x = b[i+1], val = mp[x], rx = re[x], sum = rx * val;
		if(val > 0){
			pq.em(stc{sum - rx, x, val - 1});
			--mp[x];
		}
		else ores -= rx;
		if(sz > i + 1){
			stc it = pq.top();
			while(it.v != mp[it.k]){
				pq.pop();
				it = pq.top();
			}
			mp[it.k] = 0;
			ores += it.sum;
			pq.pop();
			--sz;
		}
		res[i] = ores;
	}
	return res;
}