Submission #274418

#TimeUsernameProblemLanguageResultExecution timeMemory
274418egekabasSanta Claus (RMI19_santa)C++14
10 / 100
803 ms33120 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; int n; struct node{ int x, h, v; } a[500009]; pii seg[2000009]; set<pii> s[500009]; void build(int v, int tl, int tr){ if(tl == tr){ s[tl].clear(); seg[v] = {1e9, tl}; return; } build(2*v, tl, (tl+tr)/2); build(2*v+1, (tl+tr)/2+1, tr); seg[v] = min(seg[2*v], seg[2*v+1]); } void upd(int v, int tl, int tr, int idx){ if(idx < tl || idx > tr) return; if(idx == tl && idx == tr){ if(s[tl].empty()) seg[v].ff = 1e9; else seg[v].ff = s[tl].begin()->ff; } else{ upd(2*v, tl, (tl+tr)/2, idx); upd(2*v+1, (tl+tr)/2+1, tr, idx); seg[v] = min(seg[2*v], seg[2*v+1]); } } pii get(int v, int tl, int tr, int l, int r){ if(tr < l || r < tl) return {1e9, 1e9}; if(l <= tl && tr <= r) return seg[v]; else{ return min( get(2*v, tl, (tl+tr)/2, l, r), get(2*v+1, (tl+tr)/2+1, tr, l, r) ); } } int used[500009]; int ans[500009]; int mem[500009]; void solve(){ cin >> n; int latest = 0; for(int i = 0; i < n; ++i) cin >> a[i].x; for(int i = 0; i < n; ++i){ cin >> a[i].h; if(a[i].h == 0) latest = i; } for(int i = 0; i < n; ++i){ cin >> a[i].v; used[i] = -1; mem[i] = n+3; } build(1, 0, n); set<pii> pr; set<pii> bef; set<pii, greater<pii>> kids; for(int i = 0; i <= latest; ++i){ ans[i] = -1; if(a[i].h) kids.insert({a[i].v, i}); else pr.insert({a[i].v, i}); } int j = 0; for(int i = latest; i < n; ++i){ if(a[i].h){ pii cur = {a[i].v, i}; pii oth = get(1, 0, n, cur.ff, n); if(oth.ff < cur.ff){ s[oth.ss].insert(cur); cur = *s[oth.ss].begin(); s[oth.ss].erase(s[oth.ss].begin()); upd(1, 0, n, oth.ss); } kids.insert(cur); } while(pr.size()){ pii cur = *pr.begin(); if(kids.lower_bound({cur.ff, 1e9}) != kids.end()){ pii ki = *kids.lower_bound({cur.ff, 1e9}); kids.erase(kids.lower_bound({cur.ff, 1e9})); s[cur.ff].insert(ki); upd(1, 0, n, cur.ff); used[ki.ss] = cur.ss; mem[cur.ss] = ki.ss; pr.erase(pr.begin()); } else break; } while(j <= i && pr.empty()){ if(j > latest){ ++j; continue; } if(a[j].h == 0){ bef.insert({a[j].v, j}); ++j; } else if(used[j] == -1){ kids.erase({a[j].v, j}); if(bef.lower_bound({a[j].v, 0}) != bef.end()){ int nxt = bef.lower_bound({a[j].v, 0})->ss; bef.erase({a[nxt].v, nxt}); pr.erase({a[nxt].v, nxt}); if(mem[nxt] != n+3){ s[a[nxt].v].erase({a[mem[nxt]].v, mem[nxt]}); upd(1, 0, n, a[nxt].v); kids.insert({a[mem[nxt]].v, mem[nxt]}); used[mem[nxt]] = -1; mem[nxt] = j; } } ++j; } else{ s[a[used[j]].v].erase({a[j].v, j}); upd(1, 0, n, a[used[j]].v); pr.insert({a[used[j]].v, used[j]}); mem[used[j]] = n+3; used[j] = -1; if(bef.lower_bound({a[j].v, 0}) != bef.end()){ int nxt = bef.lower_bound({a[j].v, 0})->ss; bef.erase({a[nxt].v, nxt}); pr.erase({a[nxt].v, nxt}); if(mem[nxt] != n+3){ s[a[nxt].v].erase({a[mem[nxt]].v, mem[nxt]}); upd(1, 0, n, a[nxt].v); kids.insert({a[mem[nxt]].v, mem[nxt]}); used[mem[nxt]] = -1; mem[nxt] = j; } } while(pr.size()){ pii cur = *pr.begin(); if(kids.lower_bound({cur.ff, 1e9}) != kids.end()){ pii ki = *kids.lower_bound({cur.ff, 1e9}); kids.erase(kids.lower_bound({cur.ff, 1e9})); if(ki.ss > n) continue; s[cur.ff].insert(ki); upd(1, 0, n, cur.ff); used[ki.ss] = cur.ss; mem[cur.ss] = ki.ss; pr.erase(pr.begin()); } else break; } ++j; } } if(j == 0) ans[i] = -1; else{ ans[i] = 2*a[i].x-a[j-1].x; } } for(int i = n-1; i >= 1; --i) if(a[i].x == a[i-1].x) ans[i-1] = ans[i]; for(int i = 0; i < n; ++i) cout << ans[i] << ' '; cout << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int t; cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...