Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
934 B
6
Indexable
Never
vector<int> solve(a,l,k) {
    auto balance = [&]() {
        while ((int)small.size() >= l) {
            large.insert(*--small.end());
            small.erase(--small.end());
        }

        while ((int)small.size() < l-1) {
            small.insert(*large.begin());
            large.erase(large.begin());
        }
    };

    auto add = [&](int x) {
        small.insert(x);
    };

    auto rem = [&](int x) {
        auto it = small.find(x);
        if (it != small.end())
            small.erase(it);
        else {
            it = large.find(x);
            large.erase(it);
        }
    };

    for (int i=0; i<k; i++)
        small.insert(a[i]);
    balance();
    vector<int> ret;
    for (int i=k; i<=n; i++) {
        ret.push_back( *large.begin());
        if (i < n) {
            add(a[i]);
            rem(a[i-k]);
            balance();
        }
    }
    return ans;
}
Leave a Comment