Submission

Score: 100

User: exoworldgd

Problemset: แคง (Kang)

Language: cpp

Time: 1.231 second

Submitted On: 2025-11-09 00:08:01

#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "kang.h"
#include <bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const ll inf = LLONG_MAX, mod = 1e9+7, maxn = 1e6+1;
vector<ll> capsize(vector<int> a, vector<int> b) {
    ll n=a.size(),m=b.size(),sum=0;
    vector<int> all = a;
    all.insert(all.end(),b.begin(),b.end()),sort(all.begin(),all.end()), all.erase(unique(all.begin(),all.end()),all.end());
    int sz = all.size();
    unordered_map<int,int> idx;
    idx.reserve(sz);
    for (int i = 0; i < sz; i++) idx[all[i]] = i;
    ll cnt[sz]={}, disc[sz]={};
    for (int i : a) cnt[idx[i]]++, sum += i;
    vector<ll> res(m);
    priority_queue<pair<ll,int>> pq;
    for (int i = 0; i < sz; i++) if (cnt[i]) pq.emplace(cnt[i]*(ll)all[i], i);
    vector<int> bid(m);
    for (int i = 0; i < m; i++) bid[i] = idx[b[i]];
    for (int i = 0; i < m; i++) {
        int id = bid[i];
        if (!disc[id]) sum += b[i], cnt[id]++, pq.emplace(cnt[id]*(ll)all[id], id);
        while (!pq.empty()) {
            auto [l,r] = pq.top(); pq.pop();
            if (disc[r] || cnt[r]*(ll)all[r] != l) continue;
            disc[r] = 1, sum -= l;
            break;
        }
        res[i] = sum;
    }
    return res;
}