#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 96068 + 123;
int n;
int x[N], type[N], val[N];
int res[N];
int sum[4 * N], min_sum[4 * N];
int taken[N];
void add(int i, int l, int r, int pos, int delta) {
if (r - l == 1) {
sum[i] += delta;
min_sum[i] += delta;
} else {
int mid = (l + r) / 2;
if (pos < mid) {
add(2 * i, l, mid, pos, delta);
} else {
add(2 * i + 1, mid, r, pos, delta);
}
sum[i] = sum[2 * i] + sum[2 * i + 1];
min_sum[i] = min(min_sum[2 * i], sum[2 * i] + min_sum[2 * i + 1]);
}
}
void go(int l, int t) {
if (type[l] == 1) {
add(1, 0, n, val[l], -1 * t);
if (taken[l] != -1) {
add(1, 0, n, taken[l], 1 * t);
}
}
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i];
}
for (int i = 0; i < n; i++) {
cin >> type[i];
}
for (int i = 0; i < n; i++) {
cin >> val[i];
}
vector<int> vals;
for (int i = 0; i < n; i++) {
vals.push_back(val[i]);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 0; i < n; i++) {
val[i] = lower_bound(vals.begin(), vals.end(), val[i]) - vals.begin();
}
int need = 0;
for (int i = 0; i < n; i++) {
if (type[i] == 0) {
need++;
type[i] = -1;
}
}
multiset<int> s;
for (int i = 0; i < n; i++) {
if (type[i] == -1) {
s.insert(val[i]);
} else {
auto it = s.lower_bound(val[i]);
if (it != s.end()) {
taken[i] = *it;
s.erase(it);
} else {
taken[i] = -1;
}
}
}
for (int i = 0; i < 4 * n; i++) {
sum[i] = 0;
min_sum[i] = 0;
}
int r = n;
for (int i = 0; i < n; i++) {
if (type[i] == -1) {
need--;
}
add(1, 0, n, val[i], type[i]);
if (need == 0 && min_sum[1] >= 0) {
r = i;
break;
}
}
for (int i = 0; i < r; i++) {
res[i] = -1;
}
int l = 0;
for (; r < n; r++) {
while (l < r) {
go(l, 1);
if (min_sum[1] < 0) {
go(l, -1);
break;
}
l++;
}
res[r] = 2 * x[r] - x[l];
if (r + 1 != n) {
add(1, 0, n, val[r + 1], 1);
}
}
for (int i = 0; i < n; i++) {
cout << res[i] << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
8 ms |
488 KB |
Output is correct |
4 |
Correct |
20 ms |
668 KB |
Output is correct |
5 |
Correct |
45 ms |
984 KB |
Output is correct |
6 |
Correct |
74 ms |
1572 KB |
Output is correct |
7 |
Correct |
136 ms |
2816 KB |
Output is correct |
8 |
Correct |
215 ms |
4120 KB |
Output is correct |
9 |
Correct |
274 ms |
7136 KB |
Output is correct |
10 |
Runtime error |
173 ms |
13228 KB |
Execution killed with signal 11 |