Submission

Score: 52

User: Dormon

Problemset: แคง (Kang)

Language: cpp

Time: 1.928 second

Submitted On: 2025-05-27 19:01:41

#include <bits/stdc++.h>


std::vector<long long> capsize(std::vector<int> v, std::vector<int> b){
    int m = b.size();
    using namespace std;
    using ll = long long;
    unordered_map<ll, ll> ump;
    for (auto e:v)
      ump[e] += e;
    
    struct heap {
        ll key, val;
        bool operator < (const heap &o) const {
            if (val != o.val) return val < o.val;
            return key < o.key; 
        }
    };
    
    // auto print = [&](priority_queue<heap> T) -> void {
    //     while (!T.empty()){
    //         cout << T.top().key << ' ' << T.top().val << '\n';
    //         T.pop();
    //     }
    // };

    vector<ll> ans;
    ll sum = 0ll;
    for (auto e:v)
      sum += e + 0ll;
    priority_queue<heap> pq;
    for (auto [key, val]:ump)
        pq.push({key, val});

    // cout << "size = " << pq.size() << '\n';

    unordered_set<int> use;
    for (auto e:b){
        if (sum <= 0ll) break;
        sum += e + 0ll;
        // print(pq);
        // cout << "sum : " << sum << '\n';
        if (use.count(e) == 0){
            auto [key, val] = pq.top();
            while (!pq.empty() && use.count(key) != 0){
                heap T = pq.top();
                pq.pop();
                key = T.key;
                val = T.val;
                // cout << "skibidi\n";
            }
            sum -= val;
            use.insert(key);
        }
        else {
            sum -= e;
            auto [key, val] = pq.top();
            while (!pq.empty() && use.count(key) != 0){
                heap T = pq.top();
                pq.pop();
                key = T.key;
                val = T.val;
                // cout << "dopdop : " << key << ' ' << val << ' ' << pq.size() << '\n';
            }
            if (use.count(key) == 0){
                sum -= val;
                use.insert(key);
            }
        }
        ans.push_back(max(0ll, sum));
    }
    int k = ans.size();
    while (k < m){
        ans.push_back(0ll);
        k++;
    }
    return ans;
}