#include <bits/stdc++.h>
using namespace std;
#define mid ((s+e)>>1)
struct node{ ///range add range min
int s,e;
node *l,*r;
int v, lazy;
node (int _s, int _e){
s = _s;
e = _e;
v = 0;
lazy = 0;
if (s!=e){
l = new node(s,mid);
r = new node(mid+1,e);
}
}
void proc(){
if (lazy==0) return;
if (s!=e){
l->lazy += lazy;
r->lazy += lazy;
}
v += lazy;
lazy = 0;
}
void upd(int a,int b, int val){
//printf("valled upd %d %d %d on %d %d\n",a,b,v,s,e);
proc();
if (a<=s && e<=b){
lazy += val;
proc();
if (s!=e){
l->proc();r->proc();
v = min(l->v,r->v);
}
return;
}
if (b<=mid){
l->upd(a,b,val);
}
else if (a>mid){
r->upd(a,b,val);
}
else {
l->upd(a,b,val);
r->upd(a,b,val);
}
proc();
l->proc();
r->proc();
v = min(l->v,r->v);
//printf("val of %d %d is now %d\n",s,e,v);
}
int query(int a, int b){
//printf("called query %d %d on %d %d\n",a,b,s,e);
//printf("v of %d %d is %d\n",s,e,v);
proc();
if (a<=s && e<=b){
return v;
}
if (b<=mid){
return l->query(a,b);
}
if (a>mid){
return r->query(a,b);
}
return min(l->query(a,b),r->query(a,b));
}
}*root;
int T;
int n;
int pos[97000];
int val[97000];
bool iself[97000];
int lastelf = 0;
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
lastelf = 0;
root = new node(0,n+1);
for (int x = 0; x<n; x++){
scanf("%d",&pos[x]);
}
for (int x = 0; x<n; x++){
int t;
scanf("%d",&t);
if (t){
iself[x] = false;
}
else {
iself[x] = true;
lastelf = x;
}
}
for (int x = 0; x<n; x++){
scanf("%d",&val[x]);
}
for (int x = 0; x<n; x++){
if (iself[x]){
root->upd(val[x],n+1,-1);
}
}
multiset<int> frontelfs;
int lp = 0;
for (int x = 0; x<n; x++){
if (!iself[x]){
root->upd(val[x],n+1,1);
//printf("root v %d\n",root->v);
}
int res = root->query(0,n+1);
/*printf("segtree now: ");
for (int x = 0; x<n; x++){
printf("%d ",root->query(x,x));
}
printf("\n");*/
//printf("\nres was %d\n",res);
while (res>=0){
//printf("loop \n");
if (lp>x) break;
if (iself[lp]){
frontelfs.insert(val[lp]);
}
else{
auto it = frontelfs.lower_bound(val[lp]);
if (it!=frontelfs.end()){
root->upd((*it),n+1,1);
frontelfs.erase(it);
}
root->upd(val[lp],n+1,-1);
}
lp++;
res = root->query(0,n+1);
//printf("res now %d\n",res);
}
//printf("lp is %d\n",lp);
if (lp==0||x<lastelf){
printf("-1 ");
continue;
}
printf("%d ",2*pos[x]-pos[lp-1]);
//printf("\n");
}
printf("\n");
}
}
Compilation message
santa.cpp: In function 'int main()':
santa.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&T);
~~~~~^~~~~~~~~
santa.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
santa.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&pos[x]);
~~~~~^~~~~~~~~~~~~~
santa.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
santa.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&val[x]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
34 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
68 ms |
6648 KB |
Output is correct |
| 6 |
Correct |
113 ms |
10488 KB |
Output is correct |
| 7 |
Correct |
221 ms |
18296 KB |
Output is correct |
| 8 |
Correct |
351 ms |
28024 KB |
Output is correct |
| 9 |
Correct |
441 ms |
34936 KB |
Output is correct |
| 10 |
Correct |
652 ms |
49608 KB |
Output is correct |
