Submission #259600

#	Time	Username	Problem	Language	Result	Execution time	Memory
259600		tqbfjotld	Santa Claus (RMI19_santa)	C++14	100 / 100	652 ms	49608 KiB

santa

#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 (stderr)

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]);
             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100