Submission #443557

#TimeUsernameProblemLanguageResultExecution timeMemory
443557valerikkSanta Claus (RMI19_santa)C++17
100 / 100
401 ms8364 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 5e5; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...