#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;
explicit Node(int _suff = 0, int _sum = 0) {
suff = _suff;
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(min(b.suff, b.sum + a.suff), a.sum + b.sum);
}
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;
}
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];
}
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));
big.insert(*it);
small.erase(it);
}
while(small.size() < sz) {
auto it = big.begin();
st.update(1, 1, n, *it, Node(-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));
gifts_so_far++;
}
else {
small.insert(val[i]);
st.update(1, 1, n, val[i], Node(-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));
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));
}
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.aint[1];
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));
have.insert(eval);
gifts_given--;
}
small.insert(val[pos]);
st.update(1, 1, n, val[pos], Node(-1, -1));
}
}
balance(gifts - gifts_given);
break;
}
pos++;
}
cout << max(-1, 2 * x[i] - best) << " ";
}
cout << "\n";
}
return 0;
}
Compilation message
santa.cpp: In lambda function:
santa.cpp:91:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(small.size() > sz) {
~~~~~~~~~~~~~^~~~
santa.cpp:97:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(small.size() < sz) {
~~~~~~~~~~~~~^~~~
santa.cpp: In function 'int main()':
santa.cpp:149:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(gifts - gifts_given <= small.size() + big.size()) {
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
santa.cpp:155:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cur.suff >= 0 && gifts - gifts_given <= small.size() + big.size()) {
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
376 KB |
Output is correct |
| 3 |
Correct |
16 ms |
504 KB |
Output is correct |
| 4 |
Correct |
34 ms |
732 KB |
Output is correct |
| 5 |
Correct |
72 ms |
1080 KB |
Output is correct |
| 6 |
Correct |
117 ms |
1404 KB |
Output is correct |
| 7 |
Correct |
208 ms |
2368 KB |
Output is correct |
| 8 |
Correct |
324 ms |
3540 KB |
Output is correct |
| 9 |
Correct |
435 ms |
6164 KB |
Output is correct |
| 10 |
Correct |
654 ms |
6704 KB |
Output is correct |
