Submission #199222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199222	2020-01-30T10:35:07 Z	popovicirobert	Santa Claus (RMI19_santa)	C++14	100 / 100	319 ms	6268 KB

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 pref, sum;
    explicit Node(int _pref = 0, int _sum = 0) {
        pref = _pref;
        sum = _sum;
    }
};
 
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(max(a.pref, a.sum + b.pref), a.sum + b.sum);
    }
 
    void update(int nod, int left, int right, int pos, Node cur) {
        if(left == right) {
            aint[nod].pref += cur.pref;
            aint[nod].sum += cur.sum;
        }
        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]);
        }
    }
};
 
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];
        }

        int gifts_given = 0, gifts_so_far = 0;
 
        multiset <int> have;
        SegTree st; st.init(n);
 
        int pos = 0, best = INF + 5;
        for(i = 1; i <= n; i++) {
            if(h[i] == 0) {
                st.update(1, 1, n, val[i], Node(1, 1));
                gifts_so_far++;
            }
            else {
                st.update(1, 1, n, val[i], Node(-1, -1));
            }

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

            while(pos < i) {
                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, eval, Node(-1, -1));
                            have.erase(it), gifts_given++;
                        }
                        st.update(1, 1, n, val[pos], Node(1, 1));
                    }
                }

                if(st.aint[1].pref <= 0) {
                    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));
                                have.insert(eval), gifts_given--;
                            }
                            st.update(1, 1, n, val[pos], Node(-1, -1));
                        }
                    }
                    break;
                }

                pos++;
            }

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	6 ms	376 KB	Output is correct
3	Correct	11 ms	376 KB	Output is correct
4	Correct	20 ms	504 KB	Output is correct
5	Correct	40 ms	808 KB	Output is correct
6	Correct	62 ms	1088 KB	Output is correct
7	Correct	116 ms	2008 KB	Output is correct
8	Correct	180 ms	3192 KB	Output is correct
9	Correct	220 ms	5508 KB	Output is correct
10	Correct	319 ms	6268 KB	Output is correct