Submission #199175

#	Time	Username	Problem	Language	Result	Execution time	Memory
199175		popovicirobert	Santa Claus (RMI19_santa)	C++14	100 / 100	662 ms	8576 KiB

santa

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;

const int INF = 1e9 + 5;

struct Node {
    int suff, sum, cnt;
    explicit Node(int _suff = 0, int _sum = 0, int _cnt = 0) {
        suff = _suff;
        sum = _sum;
        cnt = _cnt;
    }
};

struct SegTree {
    vector <Node> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        int pw = 1;
        while(pw < 2 * n) {
            pw *= 2;
        }
        aint.resize(pw + 1);
    }

    inline Node combine(Node a, Node b) {
        return Node(min(b.suff, b.sum + a.suff), a.sum + b.sum, a.cnt + b.cnt);
    }

    void update(int nod, int left, int right, int pos, Node cur) {
        if(left == right) {
            aint[nod].suff += cur.suff;
            aint[nod].sum += cur.sum;
            aint[nod].cnt += cur.cnt;
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, cur);
            else update(2 * nod + 1, mid + 1, right, pos, cur);
            aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
        }
    }

    Node query(int nod, int left, int right, int cnt) {
        if(cnt <= 0) return Node(INF, 0, 0);
        if(cnt >= aint[nod].cnt) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            Node ans = combine(query(2 * nod + 1, mid + 1, right, cnt),
                      query(2 * nod, left, mid, cnt - aint[2 * nod + 1].cnt));
            return ans;
        }
    }
};

int main() {
#ifdef HOME
    ifstream cin("input.txt");
    ofstream cout("output.txt");
#endif
    int t, i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t;

    while(t--) {
        cin >> n;

        vector <int> x(n + 1), h(n + 1), val(n + 1);
        for(i = 1; i <= n; i++) {
            cin >> x[i];
        }
        int gifts = 0;
        for(i = 1; i <= n; i++) {
            cin >> h[i];
            gifts += 1 - h[i];
        }
        for(i = 1; i <= n; i++) {
            cin >> val[i];
        }

        vector <int> ord(n);
        iota(ord.begin(), ord.end(), 1);
        sort(ord.begin(), ord.end(), [&](const int &a, const int &b) {
                if(val[a] == val[b]) return h[a] < h[b];
                return val[a] > val[b];
        });

        for(i = 0; i < n; i++) {
            val[ord[i]] = n - i;
        }

        multiset <int> have, small, big;
        SegTree st; st.init(n);

        auto balance = [&](int sz) {
            while(small.size() > sz) {
                auto it = prev(small.end());
                st.update(1, 1, n, *it, Node(1, 1, -1));
                big.insert(*it);
                small.erase(it);
            }
            while(small.size() < sz) {
                auto it = big.begin();
                st.update(1, 1, n, *it, Node(-1, -1, 1));
                small.insert(*it);
                big.erase(it);
            }
        };

        int best = INF + 1;
        int pos = 0, gifts_so_far = 0, gifts_given = 0;

        for(i = 1; i <= n; i++) {
            if(h[i] == 0) {
                st.update(1, 1, n, val[i], Node(1, 1, 1));
                gifts_so_far++;
            }
            else {
                small.insert(val[i]);
                st.update(1, 1, n, val[i], Node(-1, -1, 1));
            }

            if(gifts_so_far < gifts || i < 2 * gifts) {
                cout << -1 << " ";
                continue;
            }

            while(pos < i) {
                balance(gifts - gifts_given);

                int eval = -1;
                if(pos != 0) {
                    if(h[pos] == 0) {
                        have.insert(val[pos]);
                    }
                    else {
                        auto it = have.lower_bound(val[pos]);
                        if(it != have.end()) {
                            eval = *it;
                            st.update(1, 1, n, *it, Node(-1, -1, -1));
                            have.erase(it);
                            gifts_given++;
                        }
                        if(small.find(val[pos]) != small.end()) {
                            small.erase(small.find(val[pos]));
                            st.update(1, 1, n, val[pos], Node(1, 1, -1));
                        }
                        else if(big.find(val[pos]) != big.end()) {
                            big.erase(big.find(val[pos]));
                        }
                    }
                }
                
                if(gifts - gifts_given <= small.size() + big.size()) {
                    balance(gifts - gifts_given);
                }

                auto cur = st.query(1, 1, n, 2 * (gifts - gifts_given));

                if(cur.suff >= 0 && gifts - gifts_given <= small.size() + big.size()) {
                    best = x[pos + 1];
                }
                else {
                    if(pos != 0) {
                        if(h[pos] == 0) {
                            have.erase(have.find(val[pos]));
                        }
                        else {
                            if(eval != -1) {
                                st.update(1, 1, n, eval, Node(1, 1, 1));
                                have.insert(eval);
                                gifts_given--;
                            }
                            small.insert(val[pos]);
                            st.update(1, 1, n, val[pos], Node(-1, -1, 1));
                        }
                    }
                    balance(gifts - gifts_given);
                    break;
                }

                pos++;
            }

            cout << max(-1, 2 * x[i] - best) << " ";
        }

        cout << "\n";
    }   

    return 0;
}

Compilation message (stderr)

santa.cpp: In lambda function:
santa.cpp:106:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(small.size() > sz) {
                   ~~~~~~~~~~~~~^~~~
santa.cpp:112:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(small.size() < sz) {
                   ~~~~~~~~~~~~~^~~~
santa.cpp: In function 'int main()':
santa.cpp:164:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(gifts - gifts_given <= small.size() + big.size()) {
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
santa.cpp:170:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(cur.suff >= 0 && gifts - gifts_given <= small.size() + big.size()) {
                                     ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100