Submission

Score: 76

User: sukritp5

Problemset: แคง (Kang)

Language: cpp

Time: 1.789 second

Submitted On: 2026-04-15 14:41:25

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MXN=1e6+7;
pair<ll,int> tree[4*MXN];

void update(int idx,ll val,int dl,int dr,int v){
  if(dl==dr)tree[v]={val,idx};
  else{
    int mid=(dl+dr)/2;
    if(idx<=mid){
      update(idx,val,dl,mid,2*v);
    }
    else update(idx,val,mid+1,dr,2*v+1);
    tree[v]=max(tree[2*v],tree[2*v+1]);
  }
}

set<int> s;
unordered_map<int,pair<int,int>> mp;//idx,cnt
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B) {
  vector<ll> ans;
  int N=A.size(),K=B.size();
  int now=1;
  ll sum=0;
  for(auto x:A){
    if(mp[x].second==0)mp[x]={now++,1};
    else mp[x].second++;
    update(mp[x].first,(ll)x*mp[x].second,1,N+K,1);
    sum+=x;
  }
  //sum = 27
  for(auto x:B){
    if(s.count(mp[x].first)){
      sum-=tree[1].first;
      // cout<<tree[1].first<<' ';
      s.insert(tree[1].second);
      update(tree[1].second,0,1,N+K,1);
      
      // cout<<tree[1].first<<' ';
      //cout<<"!1 ";
    }
    else if(mp[x].first==0){
      update(now,x,1,N+K,1);
      mp[x]={now++,1};
      sum+=(ll)x-tree[1].first;
      s.insert(tree[1].second);
      update(tree[1].second,0,1,N+K,1);
      //cout<<"!2 ";
    }
    else if((ll)x*(mp[x].second+1)>=tree[1].first){
      update(mp[x].first,0,1,N+K,1);
      s.insert(mp[x].first);
      sum-=(ll)x*mp[x].second;
      //cout<<"!3 ";
    }
    else{
      mp[x].second++;
      update(mp[x].first,(ll)x*mp[x].second,1,N+K,1);
      sum+=(ll)x-tree[1].first;
      s.insert(tree[1].second);
      update(tree[1].second,0,1,N+K,1);
      //cout<<"!4 ";
    }
    //cout<<tree[1].first<<' ';
    ans.emplace_back(sum);
  }
  return ans;
}