Submission

Score: 76

User: kungarooo

Problemset: แคง (Kang)

Language: cpp

Time: 2.058 second

Submitted On: 2025-08-02 23:39:16

#include <bits/stdc++.h>
using namespace std;
long long int sum=0;
unordered_map<long long int,long long int> c;
// long long wdym(int d){

//     long long int sub=0;
//     for(int i=0;i<d&&!pq.empty();i++){
//         sub+=pq.top();
//         pq.pop();
//     }
//     return sum-sub;
// }
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B){
    int m=B.size();
    
    sort(A.begin(),A.end());
    vector<int> BB=B;
    sort(BB.begin(),BB.end());
    for(int i=0;i<A.size();){
        int idx=i;
        while(++i<A.size()&&A[i]==A[idx]){}
        c[A[idx]]=A[idx]*((long long int)(i-idx));
        sum+=A[idx]*((long long int)(i-idx));
    }
    for(int i=0;i<BB.size();){
        int idx=i;
        while(++i<BB.size()&&BB[i]==BB[idx]){}
        c[BB[idx]]+=BB[idx]*((long long int)(i-idx));
        sum+=BB[idx]*((long long int)(i-idx));
    }

    priority_queue<pair<long long int,long long int>> pq;
    multiset<long long int> l;
    for(auto i:c){
        //l.insert(i.second);
        pq.push({i.second,i.first});
    }
    long long int sub=0;
    for(int j=0;j<m&&!pq.empty();j++){
        sub+=pq.top().first;
        l.insert(pq.top().first);
        //in[pq.top().second]=1;
        pq.pop();
    }
    // for(auto i:l){
    //     cout<<i<<" ";
    // }
    // cout<<"\n";
    vector<long long> ret;
    for(int i=m;i>=1;i--){
        ret.push_back(sum-sub);
        long long int tt=c[B[i-1]];
        bool wtf=(l.find(tt)!=l.end());
        if(wtf)l.erase(l.find(tt));
        //cout<<i<<" "<<c[B[i-1]]<<"hiii\n";
        c[B[i-1]]-=B[i-1];
        tt-=B[i-1];
        if(wtf)l.insert(tt);
        sum-=B[i-1];
        if(wtf)sub-=B[i-1];
        if(l.size()>=i){
            sub-=*(l.begin());
            l.erase((l.begin()));
        }

        // for(auto i:l){
        //     cout<<i<<": ";
        // }
        // cout<<"\n";
        //cout<<sum<<" "<<sub<<"\n";
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
// int32_t main(){
//     int n, m;
//     cin >> n >> m;
//     vector<int> A(n), B(m);
//     for(auto &x: A) cin >> x;
//     for(auto &x: B) cin >> x;
//     vector<long long> ans =  capsize(A,B);
//     for(auto x: ans){
//         cout << x <<" ";
//     }
// }
/*
5 4
6 3 9 6 3
4 6 9 6
*/