Submission

Score: 0

User: preum101

Problemset: แคง (Kang)

Language: cpp

Time: 2.106 second

Submitted On: 2026-03-26 20:03:14

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

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

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

    int 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(int tar, long long add, int cl, int cr, int v) {
    if (tar>cr || tar<cl) {return ;}
    if (cl==tar && cr==tar) {tree[v] = {tree[v].first+add,tree[v].second}; return ;}

    int 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) {

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

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

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

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

    for (int 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<int> cut;
    for (int 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.push_back(cnt);
    }

    return C;
}

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