Submission #259592

#	Time	Username	Problem	Language	Result	Execution time	Memory
259592		dvdg6566	Santa Claus (RMI19_santa)	C++14	0 / 100	1088 ms	28920 KiB

santa

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 100010;
const ll BSIZ= 800;

struct node{
    ll s,e,m,v,rp;
    node *l,*r;
    node(ll _s,ll _e):s(_s),e(_e){
        m=(s+e)/2;
        rp=0;
        v=1e9;
        if(s!=e){l=new node(s,m);r=new node(m+1,e);}
    }
    void up(ll x,ll val){
        if(s==e){
            rp+=val;
            if(rp)v=s;
            else v=1e9;
            return;
        }
        if(x<=m)l->up(x,val);
        else r->up(x,val);
        v=min(l->v,r->v);
    }
    ll ask(ll x,ll y){
        if(s==x&&e==y)return v;
        if(y<=m)return l->ask(x,y);
        else if(x>m)return r->ask(x,y);
        else return min(l->ask(x,m),r->ask(m+1,y));
    }
    void reset(){
        v=1e9;
        if(s==e)return;
        l->reset();r->reset();
    }
}*root;

ll N,T;

struct node2{
    ll s,e,m,v,lz;
    node2 *l,*r;
    node2(ll _s,ll _e):s(_s),e(_e){
        m=(s+e)/2;v=0;lz=0;
        if(s!=e){l=new node2(s,m);r=new node2(m+1,e);}
    }
    ll minq(ll x,ll y){
        if(s==x&&e==y)return v+lz;
        if(y<=m)return l->minq(x,y)+lz;
        else if(x>m)return r->minq(x,y)+lz;
        else return max(l->minq(x,m),r->minq(m+1,y))+lz;
    }
    void up(ll x,ll y,ll val){
        if(s==x&&e==y){lz+=val;return;}
        if(y<=m)l->up(x,y,val);
        else if(x>m)r->up(x,y,val);
        else{
            l->up(x,m,val);r->up(m+1,y,val);
        }
        v=max(l->v+l->lz,r->v+r->lz);   
    }
    void reset(){
        v=lz=0;
        if(s==e)return;
        l->reset();
        r->reset();
    }
    void db(ll k){
        if(s==e){cout<<v+k+lz<<' ';return;}
        l->db(k+lz);
        r->db(k+lz);
        if(s==1&&e==N)cout<<'\n';
    }
}*root2;


ll X[MAXN],H[MAXN],V[MAXN];
ll D[MAXN],S[MAXN],M[MAXN];
ll W[MAXN];

int main(){
    cin>>T;
    while(T--){
        cin>>N;
        root=new node(1,N);
        root2=new node2(1,N);

        for(ll i=1;i<=N;++i)cin>>X[i];
        for(ll i=1;i<=N;++i)cin>>H[i];
        for(ll i=1;i<=N;++i)cin>>V[i];
        memset(D,0,sizeof(D));
        memset(W,0,sizeof(W));
        ll lastz=0;
        for(ll i=1;i<=N;++i)if(!H[i])lastz=max(lastz,i);
        for(ll i=1;i<=lastz;++i)D[i]=-1;
        ll L=0;

        for(ll i=1;i<=N;++i){
            if(!H[i]){
                M[i]=1e9;
                ++L;
                root->up(V[i],1);
                // cerr<<"Update "<<V[i]<<' '<<1<<'\n';
            }else{
                ll val=root->ask(V[i],N);
                M[i]=val;
                // cerr<<"Value "<<V[i]<<" match with "<<val<<'\n';
                if(val!=1e9){
                    root->up(val,-1);
                    --L;   
                }
            }
            if(L==0&&D[i]==0)W[i]=X[i];
        }
        // for(ll i=1;i<=N;++i)cout<<M[i]<<' ';cout<<'\n';

        // for(ll EN=1;EN<=lastz;++EN){
        //     if(!H[EN])root2->up(V[EN],N,1);
        //     else root2->up(V[EN],N,-1);
        // }

        ll ST=0;
        for(ll EN=lastz+1;EN<=N;++EN){
            D[EN]=3e9;
            for(ll ST=1;ST<=EN;++ST){
                root->reset();root2->reset();
                for(int i=1;i<ST;++i){
                    if(H[i]==0){
                        root->up(V[i],1);
                        root2->up(V[i],N,1);
                    }else{
                        int k=root->ask(V[i],N);
                        if(k!=1e9)root2->up(k,N,-1);
                    }
                }
                for(int i=ST;i<=EN;++i){
                    if(H[i]==0){
                        root2->up(V[i],N,1);
                    }else{
                        root2->up(V[i],N,-1);
                    }
                }
                // cerr<<ST<<' '<<EN<<' '<<root2->minq(1,N)<<'\n';
                if(root2->minq(1,N)>0)continue;
                D[EN]=min(D[EN],X[EN]*2-X[ST]);
            }        
            if(D[EN]==3e9)D[EN]=-1;
        }


        for(ll i=1;i<=N;++i){
            // if(W[i]!=0)assert(W[i]==D[i]);
            cout<<D[i]<<' ';
        }

        cout<<'\n';
        // return 0;
    }
}

Compilation message (stderr)

santa.cpp: In function 'int main()':
santa.cpp:137:12: warning: unused variable 'ST' [-Wunused-variable]
         ll ST=0;
            ^~

• Subtask 1: 0 / 100