Submission

Score: 100

User: foldnut

Problemset: แคง (Kang)

Language: cpp

Time: 0.994 second

Submitted On: 2026-03-31 21:32:36

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<ll> capsize(vector<int> a, vector<int> b){
  int n = a.size(), m = b.size();
  vector<ll> ans(m), compress, v(n + m), fq(n + m, 0);
  vector<bool> in(n + m, 0);
  compress.reserve(n + m);
  priority_queue<pair<ll, ll>> pq;
  for(int i = 0;i<n;i++) compress.push_back(a[i]);
  for(int i = 0;i<m;i++) compress.push_back(b[i]);
  sort(compress.begin(), compress.end());
  for(int i = 0;i<n;i++){
    auto id = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin();
    v[id] = a[i];
    a[i] = id;
  }
  for(int i = 0;i<m;i++){
    auto id = lower_bound(compress.begin(), compress.end(), b[i]) - compress.begin();
    v[id] = b[i];
    b[i] = id;
  }
  ll sm = 0, r = 0;
  for(int i = 0;i<n;i++) fq[a[i]]++;
  for(int i = 0;i<n + m;i++){
    if(fq[i] == 0) continue;
    pq.push({v[i] * fq[i], i});
    sm += v[i] * fq[i];
  }
  for(int i = 0;i<m;i++){
    sm += v[b[i]];
    if(in[b[i]]){
      r += v[b[i]];
    }else{
      pq.push({++fq[b[i]] * v[b[i]], b[i]});
    }
    while(!pq.empty()){
      if(!in[pq.top().second]) break;
      pq.pop();
    }
    if(!pq.empty()){
      r += pq.top().first;
      in[pq.top().second] = 1;
      pq.pop();
    }
    ans[i] = sm - r;
  }
  return ans;
}