제출 #581611

#제출 시각아이디문제언어결과실행 시간메모리
581611JovanBSanta Claus (RMI19_santa)C++17
100 / 100
250 ms13252 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 100000; struct Segment{ int mn, sum; } seg[4*N+5]; void mrg(int node){ seg[node].sum = seg[node*2].sum + seg[node*2+1].sum; seg[node].mn = min(seg[node*2].mn, seg[node*2].sum + seg[node*2+1].mn); } void init(int node, int l, int r){ seg[node].mn = seg[node].sum = 0; if(l == r) return; int mid = (l+r)/2; init(node*2, l, mid); init(node*2+1, mid+1, r); } void upd(int node, int l, int r, int x, int t){ if(l == r){ seg[node].mn += t; seg[node].sum += t; return; } int mid = (l+r)/2; if(x <= mid) upd(node*2, l, mid, x, t); else upd(node*2+1, mid+1, r, x, t); mrg(node); } multiset <int> q; int sol[N+5]; int x[N+5], h[N+5], val[N+5]; void solve(){ int n; cin >> n; init(1, 1, n + 1); for(int i=1; i<=n; i++){ cin >> x[i]; } int last = 0; for(int i=1; i<=n; i++){ cin >> h[i]; if(!h[i]) last = i; } for(int i=1; i<=n; i++){ cin >> val[i]; val[i]++; } for(int i=1; i<=last; i++){ if(h[i]) upd(1, 1, n + 1, val[i], 1); else upd(1, 1, n + 1, val[i], -1); } q.clear(); int j = 1; for(int i=last; i<=n; i++){ if(i != last) upd(1, 1, n + 1, val[i], 1); while(j < i){ if(!h[j]){ q.insert(val[j]); j++; continue; } auto c = q.lower_bound(val[j]); if(c == q.end()){ upd(1, 1, n + 1, val[j], -1); if(seg[1].mn < 0){ upd(1, 1, n + 1, val[j], 1); break; } j++; continue; } upd(1, 1, n + 1, *c, 1); upd(1, 1, n + 1, val[j], -1); if(seg[1].mn >= 0) q.erase(c); else{ upd(1, 1, n + 1, *c, -1); upd(1, 1, n + 1, val[j], 1); break; } j++; } if(seg[1].mn < 0) sol[i] = -1; else sol[i] = 2*x[i] - x[j]; } for(int i=1; i<=n; i++){ if(i < last) cout << "-1 "; else cout << sol[i] << " "; } cout << "\n"; } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int t; cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...