Submission

Score: 100

User: meme_boi2

Problemset: แคง (Kang)

Language: cpp

Time: 1.877 second

Submitted On: 2026-04-20 21:39:26

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void print(priority_queue<pair<ll,ll>> pq){
    while(!pq.empty()){
        auto [val,x] = pq.top();
        pq.pop();
        cout << "Priority Queue : " << '{' << val << ',' << x << '}' << ' ';
    }
    cout << '\n';
}

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B){
    unordered_map<ll,ll> mp, vis;
    ll sum = 0ll;
    for(auto x: A){
        mp[x]++;
        //vis[x] = 1;
        sum += x;
    }
    priority_queue<pair<ll,ll>> pq;
    for(auto [x,y] : mp){
        pq.push({x * y, x}); // value * freq, value 
    }
    vector<ll> ans;
    for(auto x: B){
       
       // cout << sum << '\n';
        
        if(vis.find(x) == vis.end()){ll freq = ++mp[x];  sum += x; pq.push({1ll * x * freq,1ll *  x});}
       // print(pq);
      // cout << vis.find(4)->second << '\n';
        while(!pq.empty() && vis.find(pq.top().second) != vis.end()) {
            pq.pop();
        }
        if(!pq.empty()){
            sum -= pq.top().first;
            vis[pq.top().second] = 1;
            pq.pop();
        }
        ans.push_back(sum);
    }
    return ans;
}
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
*/