제출 #274787

#제출 시각아이디문제언어결과실행 시간메모리
274787Atill83Santa Claus (RMI19_santa)C++14
90 / 100
1093 ms13932 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 1e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; int t[4*MAXN]; int lazy[4*MAXN]; void push(int v){ t[2*v] += lazy[v]; t[2*v + 1] += lazy[v]; lazy[2*v] += lazy[v]; lazy[2*v + 1] += lazy[v]; lazy[v] = 0; } void build(int v, int l, int r){ if(l == r){ t[v] = 0; lazy[v] = 0; }else{ build(2*v, l, (l + r) / 2); build(2*v + 1, (l + r) / 2 + 1, r); t[v] = 0; lazy[v] = 0; } } void upd(int v, int tl, int tr, int l, int r, int val){ if(l > r) return; else if(l == tl && r == tr){ lazy[v] += val; t[v] += val; }else{ push(v); int tm = (tl + tr) / 2; upd(2*v, tl, tm, l, min(tm, r), val); upd(2*v + 1, tm + 1, tr, max(tm + 1, l), r, val); t[v] = min(t[2*v], t[2*v + 1]); } } int x[MAXN], h[MAXN], v[MAXN]; int cik[MAXN]; ll ans[MAXN]; void solve(){ cin>>n; for(int i = 1; i <= n; i++){ cin>>x[i]; } int lst = 0; build(1, 0, n); multiset<int> ms; for(int i = 1; i <= n; i++){ cin>>h[i]; if(h[i] == 0) lst = i; } memset(cik, -1, sizeof(cik)); for(int i = 1; i <= n; i++){ cin>>v[i]; if(h[i] == 0){ ms.insert(v[i]); }else{ auto u = ms.lower_bound(v[i]); if(u != ms.end()){ cik[i] = *u; ms.erase(u); } } } for(int j: ms){ upd(1, 0, n, j, n, -1); } int left = n; for(int i = n; i >= 1; i--){ if(i < lst){ ans[i] = -1; }else{ while(left >= i || (t[1] < 0 && left)){ if(cik[left] >= 0) upd(1, 0, n, cik[left], n, -1); if(h[left]) upd(1, 0, n, v[left], n, 1); left--; } if(t[1] < 0){ ans[i] = -1; }else{ ans[i] = 2*x[i] - x[left + 1]; } cerr<<left<<" "; upd(1, 0, n, v[i], n, - 1); } } for(int i = 1; i <= n; i++) cout<<ans[i]<<" "; cout<<endl; cerr<<endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif int t; cin>>t; while(t--) solve(); #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...