Submission

Score: 100

User: 12345678

Problemset: แคง (Kang)

Language: cpp

Time: 0.960 second

Submitted On: 2026-03-21 19:31:28

#include <bits/stdc++.h>

using namespace std;

#define ll long long

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B) {
    int n=A.size(), m=B.size(), t;
    vector<ll> res, srt;
    ll sm=0;
    priority_queue<pair<ll, ll>> pq;
    for (int i=0; i<n; i++) srt.push_back(A[i]);
    for (int i=0; i<m; i++) srt.push_back(B[i]);
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    t=srt.size();
    vector<ll> f(t+1), used(t+1), vl(t+1);
    for (int i=1; i<=t ;i++) vl[i]=srt[i-1];
    for (int i=0; i<n; i++) A[i]=lower_bound(srt.begin(), srt.end(), A[i])-srt.begin()+1;
    for (int i=0; i<m; i++) B[i]=lower_bound(srt.begin(), srt.end(), B[i])-srt.begin()+1;
    for (int i=0; i<n;i ++) sm+=vl[A[i]], f[A[i]]++;
    for (int i=1; i<=t; i++) if (f[i]) pq.push({vl[i]*f[i], i});
    for (int i=0; i<m; i++)
    {
        if (!used[B[i]]) f[B[i]]++, pq.push({vl[B[i]]*f[B[i]], B[i]}), sm+=vl[B[i]];
        while (!pq.empty())
        {
            auto [cst, idx]=pq.top();
            pq.pop();
            if (used[idx]) continue;
            sm-=cst;
            used[idx]=1;
            break;
        }
        res.push_back(sm);
    }        
    return res;
}