Submission

Score: 76

User: preum101

Problemset: แคง (Kang)

Language: cpp

Time: 2.109 second

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

#include <bits/stdc++.h>
#include "kang.h"
#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;

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

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

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

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

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

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

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

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

    for (long long i = 0; i<n; i++) {
        update(vv[A[i]],A[i],1,t,1);
        cnt += A[i];
    }
    set<long long> cut;
    for (long long 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;
}