Submission #199222

#TimeUsernameProblemLanguageResultExecution timeMemory
199222popovicirobertSanta Claus (RMI19_santa)C++14
100 / 100
319 ms6268 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...