Submission

Score: 76

User: preum101

Problemset: แคง (Kang)

Language: cpp

Time: 2.108 second

Submitted On: 2026-03-26 21:03:03

#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> C;

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]);
}

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

    ll n = A.size();
    ll m = B.size();
    C.resize(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];
    }
    set<ll> cut;
    for (ll i = 0; i<m; i++) {
        if (cut.count(B[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);

        C[i] = cnt;
        if (cnt==0) {continue;}
    }



    return C;
}