# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198574 | Akashi | Santa Claus (RMI19_santa) | C++14 | 466 ms | 14072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int SZ = 1e5 + 5;
int n, t;
int ans[SZ], x[SZ], v[SZ];
bool h[SZ];
multiset <int> s;
int Arb[SZ * 4], Lazy[SZ * 4];
void propag(int nod){
if(!Lazy[nod]) return ;
for(int i = nod * 2; i <= nod * 2 + 1 ; ++i){
Lazy[i] += Lazy[nod];
Arb[i] += Lazy[nod];
}
Lazy[nod] = 0;
}
void add(int x, int y, int val, int st = 1, int dr = n, int nod = 1){
if(x <= st && dr <= y){
Lazy[nod] += val;
Arb[nod] += val;
return ;
}
propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) add(x, y, val, st, mij, nod * 2);
if(mij + 1 <= y) add(x, y, val, mij + 1, dr, nod * 2 + 1);
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}
int main(){
//freopen("1.in", "r", stdin);
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 1; i <= n ; ++i) scanf("%d", &x[i]);
int Last_elf = 0;
for(int i = 1; i <= n ; ++i){
scanf("%d", &h[i]);
ans[i] = -1;
if(!h[i]) Last_elf = i;
}
for(int i = 1; i <= n ; ++i) scanf("%d", &v[i]);
memset(Arb, 0, sizeof(Arb));
memset(Lazy, 0, sizeof(Lazy));
int j = 1;
while(j <= Last_elf){
if(h[j]) add(v[j], n, 1);
else add(v[j], n, -1);
++j;
}
s.clear();
for(int st = 1; st <= n ; ++st){
if(j == st) add(v[j], n, 1), ++j;
while(Arb[1] < 0 && j <= n){
add(v[j], n, 1);
++j;
}
if(Arb[1] >= 0) ans[j - 1] = st;
if(h[st]){
multiset <int> :: iterator it = s.lower_bound(v[st]);
if(it != s.end()){
add(*it, n, 1);
s.erase(it);
}
add(v[st], n, -1);
}
else s.insert(v[st]);
}
ans[0] = -1;
for(int i = Last_elf + 1; i <= n ; ++i)
ans[i] = max(ans[i], ans[i - 1]);
for(int i = 1; i <= n ; ++i){
if(ans[i] == -1) printf("%d ", ans[i]);
else printf("%d ", 2 * x[i] - x[ans[i]]);
}
printf("\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |