Submission #478874

#TimeUsernameProblemLanguageResultExecution timeMemory
478874AlexandruabcdeSanta Claus (RMI19_santa)C++14
100 / 100
339 ms12100 KiB
#include <bits/stdc++.h> using namespace std; constexpr int NMAX = 1e5 + 5; int N; int X[NMAX]; int H[NMAX]; int V[NMAX]; int vf = 0; int ans[NMAX]; struct NOD { int a; int lazy; }; NOD Arbore[4*NMAX]; void Propag (int node, int a, int b) { if (a == b) return; if (Arbore[node].lazy == 0) return; int aux = Arbore[node].lazy; Arbore[2*node].lazy += aux; Arbore[2*node+1].lazy += aux; Arbore[2*node].a += aux; Arbore[2*node+1].a += aux; Arbore[node].lazy = 0; } void Update (int node, int a, int b, int ua, int ub, int val) { if (ua <= a && b <= ub) { Arbore[node].a += val; Arbore[node].lazy += val; return; } Propag(node, a, b); int mij = (a + b) / 2; if (ua <= mij) Update(2*node, a, mij, ua, ub, val); if (mij < ub) Update(2*node+1, mij+1, b, ua, ub, val); Arbore[node].a = min(Arbore[2*node].a, Arbore[2*node+1].a); } int Best () { return Arbore[1].a; } void Read () { cin >> N; for (int i = 1; i <= N; ++ i ) cin >> X[i]; for (int i = 1; i <= N; ++ i ) cin >> H[i]; for (int i = 1; i <= N; ++ i ) cin >> V[i]; } void Normalize () { map <int, int> mp; for (int i = 1; i <= N; ++ i ) mp[V[i]] = 1; vf = 0; for (auto &it : mp) it.second = ++ vf; for (int i = 1; i <= N; ++ i ) V[i] = mp[V[i]]; } void Solve () { Normalize(); int Last_Present = N; while (Last_Present >= 1 && H[Last_Present]) -- Last_Present; assert(1 <= Last_Present && Last_Present <= N); for (int i = 1; i <= N; ++ i ) ans[i] = -1; for (int i = 1; i <= Last_Present; ++ i ) if (H[i]) Update(1, 1, vf, V[i], vf, 1); else Update(1, 1, vf, V[i], vf, -1); map <int, int> S; for (int i = 1; i <= N; ++ i ) { if (i > Last_Present) { ++ Last_Present; if (H[Last_Present]) Update(1, 1, vf, V[Last_Present], vf, 1); else Update(1, 1, vf, V[Last_Present], vf, -1); } while (Last_Present < N && Best() < 0) { ++ Last_Present; if (H[Last_Present]) Update(1, 1, vf, V[Last_Present], vf, 1); else Update(1, 1, vf, V[Last_Present], vf, -1); } if (Best() >= 0) ans[Last_Present] = i; if (H[i] == 0) { S[V[i]] ++;; } else { auto it = S.lower_bound(V[i]); if (it != S.end()) { Update(1, 1, vf, it->first, vf, 1); } -- it->second; if (it->second == 0) S.erase(it); Update(1, 1, vf, V[i], vf, -1); } } for (int i = 2; i <= N; ++ i ) ans[i] = max(ans[i-1], ans[i]); for (int i = 1; i <= N; ++ i ) { if (ans[i] == -1) { cout << -1 << " "; } else cout << 2LL * X[i] - X[ans[i]] << " "; } cout << '\n'; } void Reset () { for (int i = 0; i <= N; ++ i ) ans[i] = -1; for (int i = 1; i <= 4 * N; ++ i ) Arbore[i].a = Arbore[i].lazy = 0; } void Do_Testcase () { Read(); Solve(); Reset(); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T = 1; cin >> T; for (; T; -- T ) Do_Testcase(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...