Submission

Score: 76

User: preum101

Problemset: แคง (Kang)

Language: cpp

Time: 2.106 second

Submitted On: 2026-03-26 20:56:54

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

long long loca[2000001];
pair<long long,long long> tree[8000004];
vector<long long> arr;

void bud(ll cl, ll cr, ll v) {
    if (cl==cr) {tree[v] = {0,cl}; return ;}

    ll mid = (cl+cr)/2;
    bud(cl, mid, v*2);
    bud(mid+1, cr, v*2+1);

    tree[v] = max(tree[v*2],tree[v*2+1]);
    return ;
}

void update(ll tar, long long add, ll cl, ll cr, ll v) {
    if (tar>cr || tar<cl) {return ;}
    if (cl==tar && cr==tar) {tree[v] = {tree[v].first+add,tree[v].second}; return ;}

    ll mid = (cl+cr)/2;
    update(tar, add, cl, mid, v*2);
    update(tar, add, mid+1, cr, v*2+1);

    tree[v] = max(tree[v*2],tree[v*2+1]);
}

///pair<int,int> query(int )

vector<long long> capsize(vector<int> A, vector<int> B) {

    ll n = A.size();
    ll m = B.size();
    vector<long long> C(m);
    set<ll> exs;
    map<ll,ll> vv,rv;

    for (ll i = 0; i<n; i++) exs.insert(A[i]);
    for (ll i = 0; i<m; i++) exs.insert(B[i]);

    ll c = 1;
    for (ll e : exs) {
        vv[e] = c;
        rv[c] = e;
        c++;
    }

    ll t = c-1;
    bud(1,t,1);
    ll cnt = 0;

    for (ll i = 0; i<n; i++) {
        update(vv[A[i]],A[i],1,t,1);
        cnt += A[i];
        //cout << cnt << " ";
    }
    /*cout << "\nExs ";

    for (int e : exs) cout << e << " ";

    cout << "\nTree ";
    for (int i = 1; i<=t*2; i++) cout << "[" << tree[i].first << "," << tree[i].second << "] ";
    */
    set<ll> cut;
    for (ll i = 0; i<m; i++) {

        if (cut.count(B[i])==0) {
            //cout << "\nB[i] = 0;";
            cnt += B[i];
            update(vv[B[i]],B[i],1,t,1);
        }
        cut.insert(rv[tree[1].second]);
        cnt -= tree[1].first;
        update(tree[1].second,-tree[1].first,1,t,1);
        //cout << "\nTree ";
        //for (int i = 1; i<=t*2; i++) cout << "[" << tree[i].first << "," << tree[i].second << "] ";
        //cout << cnt << " ";

        C[i] = cnt;
    }

    return C;
}

/*signed main() {
    int n;
    cin >> n;
}
*/