#include <algorithm>
#include <iostream>
#include <tgmath.h>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1e9 + 7;
const int INF = 1e9;
struct House
{
int x, h, v;
inline friend bool operator < (const House &a, const House &b)
{
return a.x < b.x || (a.x == b.x && a.h < b.h) || (a.x == b.x && a.h == b.h && a.v < b.v);
}
} houses[MAXN];
int n, t;
int x[MAXN];
int h[MAXN];
int v[MAXN];
struct Node
{
Node *left, *right;
int ones, zeros;
int value, type;
int cnt;
int y;
Node()
{
left = right = nullptr;
}
Node(int _value, int _type, int _y)
{
left = right = nullptr;
value = _value;
type = _type;
cnt = 1;
zeros = (type == 0) * cnt;
ones = (type == 1) * cnt;
y = _y;
}
};
Node *treap;
void recover(Node *curr)
{
if (curr == nullptr) return;
curr->ones = 0;
curr->zeros = 0;
if (curr->left != nullptr)
{
curr->ones = curr->left->ones;
curr->zeros = curr->left->zeros;
}
curr->ones = curr->ones + std::max(0, (curr->type == 1 ? curr->cnt : 0) - curr->zeros);
curr->zeros = (curr->type == 0 ? curr->cnt : 0) + std::max(0, curr->zeros - (curr->type == 1 ? curr->cnt : 0));
if (curr->right != nullptr)
{
curr->ones = curr->ones + std::max(0, curr->right->ones - curr->zeros);
curr->zeros = curr->right->zeros + std::max(0, curr->zeros - curr->right->ones);
}
}
inline bool cmp(std::pair <int,bool> x, std::pair <int,bool> y)
{
return x.first > y.first || (x.first == y.first && x.second < y.second);
}
void split(Node *curr, Node *&left, Node *&right, std::pair <int,bool> value)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (cmp({curr->value, curr->type}, value))
{
left = curr;
split(curr->right, left->right, right, value);
recover(left);
} else
{
right = curr;
split(curr->left, left, right->left, value);
recover(right);
}
}
void split2(Node *curr, Node *&left, Node *&right, std::pair <int,bool> value)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (value.first == curr->value && value.second == curr->type)
{
left = curr;
split2(curr->right, left->right, right, value);
recover(left);
} else
{
right = curr;
split2(curr->left, left, right->left, value);
recover(right);
}
}
void merge(Node *&curr, Node *left, Node *right)
{
if (left == nullptr)
{
curr = right;
return;
}
if (right == nullptr)
{
curr = left;
return;
}
if (left->y > right->y)
{
curr = left;
merge(curr->right, left->right, right);
} else
{
curr = right;
merge(curr->left, left, right->left);
}
recover(curr);
}
void insert(int value, bool type)
{
Node *l, *r, *rr, *rl, *r1;
split(treap, l, r, {value, type});
split2(r, rl, rr, {value, type});
if (rl == nullptr) rl = new Node(value, type, rand());
else
{
rl->cnt++;
recover(rl);
}
merge(r1, rl, rr);
merge(treap, l, r1);
}
void erase(int value, bool type)
{
Node *l, *r, *rr, *rl, *r1;
split(treap, l, r, {value, type});
split2(r, rl, rr, {value, type});
if (rl->cnt == 1) rl = nullptr;
else
{
rl->cnt--;
recover(rl);
}
merge(r1, rl, rr);
merge(treap, l, r1);
}
std::multiset <int> toGive;
int maxElvePos;
int minElveIdx;
void solve()
{
toGive.clear();
treap = nullptr;
int ptr = 0;
for (int i = 1 ; i <= n ; ++i)
{
insert(v[i], h[i]);
if (x[i] < maxElvePos || (treap != nullptr && treap->zeros != 0))
{
std::cout << -1 << ' ';
continue;
}
while (ptr + 1 < i)
{
if (h[ptr + 1] == 0)
{
toGive.insert(v[ptr + 1]);
ptr++;
continue;
} else
{
int erased = -1;
auto it = toGive.lower_bound(v[ptr + 1]);
erase(v[ptr + 1], h[ptr + 1]);
if (it != toGive.end())
{
erased = *it;
erase(*it, 0);
toGive.erase(it);
}
if (treap != nullptr && treap->zeros >= 1)
{
insert(v[ptr + 1], h[ptr + 1]);
if (erased != -1)
{
insert(erased, 0);
toGive.insert(erased);
}
break;
} else
{
ptr++;
}
}
}
std::cout << 2*x[i] - x[ptr + 1] << ' ';
}
std::cout << '\n';
}
void read()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].x;
for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].h;
for (int i = 1 ; i <= n ; ++i) std::cin >> houses[i].v;
std::sort(houses + 1, houses + 1 + n);
for (int i = 1 ; i <= n ; ++i)
{
x[i] = houses[i].x;
h[i] = houses[i].h;
v[i] = houses[i].v;
if (h[i] == 0)
{
maxElvePos = x[i];
minElveIdx = i;
}
}
}
void fastIO()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
srand(time(nullptr));
fastIO();
std::cin >> t;
while (t--)
{
read();
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
724 KB |
Output is correct |
| 4 |
Correct |
20 ms |
1320 KB |
Output is correct |
| 5 |
Correct |
46 ms |
2520 KB |
Output is correct |
| 6 |
Correct |
77 ms |
4044 KB |
Output is correct |
| 7 |
Correct |
139 ms |
7140 KB |
Output is correct |
| 8 |
Correct |
226 ms |
10708 KB |
Output is correct |
| 9 |
Correct |
250 ms |
13376 KB |
Output is correct |
| 10 |
Correct |
376 ms |
19052 KB |
Output is correct |
