POI Task Warehouse Store

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Segment {
    long long minPrefixSum, sum;
    Segment combine(const Segment &s2) const {
        Segment s;
        s.minPrefixSum = min(minPrefixSum, sum+s2.minPrefixSum);
        s.sum = sum + s2.sum;
        return s;
    }
    Segment () {}
    Segment (long long x): minPrefixSum(x), sum(x) {}
};
Segment combine(const Segment &s1, const  Segment &s2) {return s1.combine(s2);}

template <typename T>
struct Segtree {
    int n;
    vector<T> tree;
    T (*combine)(const T &, const T &);
    Segtree(T (*fCombine)(const T &, const T &)): combine(fCombine){}
    void build(const vector<T> &v) {
        n = v.size();
        tree.resize(2*n);
        for (int i = 0; i < n; ++i) tree[n+i] = v[i];
        for (int i = n-1; i > 0; --i) tree[i] = combine(tree[2*i], tree[2*i+1]);
    }
    void update(int index, T value) {
        index += n;
        tree[index] = value;
        while (index > 1) {
            if (index & 1) tree[index>>1] = combine(tree[index^1], tree[index]);
            else tree[index>>1] = combine(tree[index], tree[index^1]);
            index>>=1;
        }
    }
    T queryRoot() {
        return tree[1];
    }
};

int main() {
    int n; cin >> n;
    vector<Segment> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].sum, a[i].minPrefixSum = a[i].sum;

    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; ++i) cin >> b[i].first, b[i].second = i;
    sort(b.begin(), b.end());

    Segtree<Segment> s(combine);
    // Take next power of 2 since order of segments matters
    while (__builtin_popcount((int)a.size()) > 1) a.push_back(0);
    s.build(a);

    vector<int> accepted;
    for (auto [x, i] : b) {
        a[i].sum -= x, a[i].minPrefixSum -= x;
        s.update(i, a[i]);
        if (s.queryRoot().minPrefixSum >= 0) accepted.push_back(i+1);
        else {
            a[i].sum += x, a[i].minPrefixSum += x;
            s.update(i, a[i]);
        }
    }
    cout << accepted.size() << endl;
    sort(accepted.begin(), accepted.end());
    for (int x : accepted) cout << x << ' ';
    cout << endl;
    return 0;
}