abc373E How to Win the Election

有N个候选人和总共K张选票，目前第i个候选人的票数为A[i]。在全部选票统计完成后，如果得票数多于自己的人数小于M，则当选，可以多个人同时当选。对于每个人，输出当选需要再获得的最少票数。
1<=M<=N<=2E5, 1<=K<=1E12, 0<=A[i]<=1E12, sum(A[i])<=K

分析：对每个候选人，二分答案，假设需要的票数为x，那么最终得票为A[i]+x，大于该得票的人数记为P，则需要统计另外M-P个人的票数进行补齐，看剩下的票数是否足够。

#include <bits/stdc++.h>
using i64 = long long;

template <typename TYPE>
struct SumTreap {
    struct Node {
        TYPE data, sum;
        int rnd, siz, dup, son[2];
        Node() { data = sum = rnd = siz = dup = son[0] = son[1] = 0; }
        Node(const TYPE &d, int cnt=1) { init(d, cnt); }
        void init(const TYPE & d, int cnt) {
            data = d; dup = siz = cnt; sum = d * cnt; rnd = rand(); son[0] = son[1] = 0;
        }
    };
    SumTreap(int multi=1):multiple(multi) { reset(); }
    void setmulti(int multi) { multiple = multi; }
    int newnode(const TYPE & d, int cnt) {
        if (!reuse.empty()) {
            int r = reuse.front();
            reuse.pop_front();
            node[r].init(d, cnt);
            return r;
        }
        node.push_back({d, cnt});
        return node.size() - 1;
    }
    void reset() { root = 0; node.resize(1); reuse.clear(); }
    void maintain(int x) {
        node[x].siz = node[x].dup;
        node[x].sum = node[x].data * node[x].dup;
        if (node[x].son[0]) {
            node[x].siz += node[node[x].son[0]].siz;
            node[x].sum += node[node[x].son[0]].sum;
        }
        if (node[x].son[1]) {
            node[x].siz += node[node[x].son[1]].siz;
            node[x].sum += node[node[x].son[1]].sum;
        }
    }
    void rotate(int d, int &r) {
        int k = node[r].son[d^1];
        node[r].son[d^1] = node[k].son[d];
        node[k].son[d] = r;
        maintain(r);
        maintain(k);
        r = k;
    }
    void insert(const TYPE &data, int cnt, int &r) {
        if (r) {
            if (!(data < node[r].data) && !(node[r].data < data)) {
                if (multiple) {
                    node[r].dup += cnt;
                    maintain(r);
                }
            } else {
                int d = data < node[r].data ? 0 : 1;
                int u = node[r].son[d];
                insert(data, cnt, u);
                node[r].son[d] = u;
                if (node[node[r].son[d]].rnd > node[r].rnd) {
                    rotate(d^1, r);
                } else {
                    maintain(r);
                }
            }
        } else {
            r = newnode(data, cnt);
        }
    }
    TYPE kth(int k) {
        assert(1 <= k && k <= size());
        for (int r = root; r; ) {
            int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
            int y = node[r].dup;
            if (k <= x) {
                r = node[r].son[0];
            } else if (k <= x + y) {
                return node[r].data;
            } else {
                k -= x + y;
                r = node[r].son[1];
            }
        }
        assert(k == 0);
        return 0;
    }
    TYPE Kth(int k) {
        assert(1 <= k && k <= size());
        for (int r = root; r; ) {
            int x = node[r].son[1] ? node[node[r].son[1]].siz : 0;
            int y = node[r].dup;
            if (k <= x) {
                r = node[r].son[1];
            } else if (k <= x + y) {
                return node[r].data;
            } else {
                k -= x + y;
                r = node[r].son[0];
            }
        }
        assert(k == 0);
        return 0;
    }
    TYPE ksum(int k) {
        assert(0 <= k && k <= node[root].siz);
        TYPE ans = 0;
        for (int r = root; r && k; ) {
            int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
            int y = node[r].dup;
            if (k <= x) {
                r = node[r].son[0];
            } else if (k <= x + y) {
                ans += node[node[r].son[0]].sum + node[r].data * (k - x);
                k = 0;
            } else {
                ans += node[node[r].son[0]].sum + node[r].data * y;
                k -= x + y;
                r = node[r].son[1];
            }
        }
        return ans;
    }
    TYPE kSum(int k) {
        assert(0 <= k && k <= node[root].siz);
        TYPE ans = 0;
        for (int r = root; r && k; ) {
            int x = node[r].son[1] ? node[node[r].son[1]].siz : 0;
            int y = node[r].dup;
            if (k <= x) {
                r = node[r].son[1];
            } else if (k <= x + y) {
                ans += node[node[r].son[1]].sum + node[r].data * (k - x);
                k = 0;
            } else {
                ans += node[node[r].son[1]].sum + node[r].data * y;
                k -= x + y;
                r = node[r].son[0];
            }
        }
        return ans;
    }
    void erase(const TYPE& data, int cnt, int & r) {
        if (r == 0) return;
        int d = -1;
        if (data < node[r].data) {
            d = 0;
        } else if (node[r].data < data) {
            d = 1;
        }
        if (d == -1) {
            node[r].dup -= cnt;
            if (node[r].dup > 0) {
                maintain(r);
            } else {
                if (node[r].son[0] == 0) {
                    reuse.push_back(r);
                    r = node[r].son[1];
                } else if (node[r].son[1] == 0) {
                    reuse.push_back(r);
                    r = node[r].son[0];
                } else {
                    int dd = node[node[r].son[0]].rnd > node[node[r].son[1]].rnd ? 1 : 0;
                    rotate(dd, r);
                    erase(data, cnt, node[r].son[dd]);
                }
            }
        } else {
            erase(data, cnt, node[r].son[d]);
        }
        if (r) maintain(r);
    }
    int ltcnt(const TYPE &data) {
        int ans = 0;
        for (int r = root; r; ) {
            int x = node[r].son[0] ? node[node[r].son[0]].siz : 0;
            if (node[r].data < data) {
                ans += node[r].dup + x;
                r = node[r].son[1];
            } else if (data < node[r].data) {
                r = node[r].son[0];
            } else {
                ans += x;
                break;
            }
        }
        return ans;
    }
    int gtcnt(const TYPE &data) {
        int ans = 0;
        for (int r = root; r; ) {
            int x = node[r].son[1] ? node[node[r].son[1]].siz : 0;
            if (node[r].data < data) {
                r = node[r].son[1];
            } else if (data < node[r].data) {
                ans += node[r].dup + x;
                r = node[r].son[0];
            } else {
                ans += x;
                break;
            }
        }
        return ans;
    }
    int count(const TYPE &data) {
        for (int r = root; r; ) {
            if (data < node[r].data) {
                r = node[r].son[0];
            } else if (node[r].data < data) {
                r = node[r].son[1];
            } else {
                return node[r].dup;
            }
        }
        return 0;
    }
    std::pair<bool,TYPE> prev(const TYPE &data) {
        std::pair<bool,TYPE> ans = {false, 0};
        for (int r = root; r; ) {
            if (node[r].data < data) {
                if (ans.first) {
                    ans.second = std::max(ans.second, node[r].data);
                } else {
                    ans = {true, node[r].data};
                }
                r = node[r].son[1];
            } else {
                r = node[r].son[0];
            }
        }
        return ans;
    }       
    std::pair<bool,TYPE> next(const TYPE &data) {
        std::pair<bool,TYPE> ans = {false, 0};
        for (int r = root; r; ) {
            if (data < node[r].data) {
                if (ans.first) {
                    ans.second = std::min(ans.second, node[r].data);
                } else {
                    ans = {true, node[r].data};
                }
                r = node[r].son[0];
            } else {
                r = node[r].son[1];
            }
        }
        return ans;
    }
    std::vector<Node> node;
    std::deque<int> reuse;
    int root, multiple;
    void insert(const TYPE& data, int cnt=1) { insert(data, cnt, root); }
    void erase(const TYPE& data, int cnt=1) { erase(data, cnt, root); }
    int size() const { return root ? node[root].siz : 0; }
    int lecnt(const TYPE& data) { return size() - gtcnt(data, root); }
    int gecnt(const TYPE& data) { return size() - ltcnt(data, root); }
};

void solve() {
    i64 N, M, K;
    std::cin >> N >> M >> K;
    SumTreap<i64> tr;
    std::vector<i64> A(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        tr.insert(A[i]);
        K -= A[i];
    }

    if (N == M) {
        for (int i = 0; i < N; i++) {
            std::cout << " 0";
        }
        return;
    }

    auto check = [&](i64 cur, i64 add) {
        i64 tar = cur + add;
        int cnt1 = tr.gtcnt(tar);
        if (cnt1 >= M) {
            return false;
        }
        int cnt2 = M - cnt1;
        i64 sum2 = tr.kSum(M) - tr.kSum(cnt1);
        i64 diff = cnt2 * (tar + 1) - sum2;
        return diff + add > K;
    };

    std::vector<i64> ans(N);
    for (int i = 0; i < N; i++) {
        tr.erase(A[i]);
        i64 lo = 0, hi = 1E12, mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (check(A[i], mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        if (lo <= K) {
            ans[i] = lo;
        } else {
            ans[i] = -1;
        }
        tr.insert(A[i]);
    }

    for (int i = 0; i < N; i++) {
        std::cout << ans[i] << " ";
    }
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}