Submission #1159447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159447		tosivanmak	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	3860 ms	190864 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct SEG{
    vector<ll>seg;
    void init(ll n){
        seg.resize(4*n+5);
    }
    void upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id]+=val; return;
        }
        ll mid=(l+r)>>1;
        if(ul<=mid)upd(ul,l,mid,val,id*2); 
        else upd(ul,mid+1,r,val,id*2+1);
        seg[id]=seg[id*2]+seg[id*2+1];
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql)return 0;
        if(l>=ql&&r<=qr)return seg[id];
        ll mid=(l+r)>>1;
        return qry(ql,qr,l,mid,id*2)+qry(ql,qr,mid+1,r,id*2+1);
    }
};
struct DSU{
    vector<ll>fa,siz,val;
    void init(ll n){
        fa.resize(n+5);
        siz.resize(n+5); val.resize(n+5);
        for(int i=0;i<n+5;i++){
            fa[i]=i; siz[i]=1; val[i]=i;
        }
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite_left(ll u, ll v){
        u=root(u); v=root(v);
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u; 
        val[u]=min(val[u],val[v]);
    }
    void unite_right(ll u, ll v){
        u=root(u); v=root(v);
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u;
        val[u]=max(val[u],val[v]);
    }
    ll value(ll x){
        x=root(x);
        return val[x];
    }
    void clear(){
        fa.clear(); siz.clear(); val.clear();
    }
};
ll a[600005],b[300005],c[300005];
ll discval[600005];
vector<pair<ll,ll> > inpos[600005],outpos[600005];
ll enterin[600005],enterout[600005];
ll n; ll pos;

ll curid;
ll diff;
vector<pair<ll,ll> >disc;

ll val(pair<ll,ll> x){
    return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}

bool valid(ll st){
    // b/c pos[a[curid]] with a[curid]
    bool in=0;
    if(st<=curid&&curid<=st+n-1)in=1;
    if(in){
        ll aite=-1;
        for(int i=0;i<inpos[curid].size()-1;i++){
            if(inpos[curid][i].first<=st&&st<=inpos[curid][i+1].first){
                if(inpos[curid][i].first>=pos&&inpos[curid][i+1].first>=pos){
                    ll dff=inpos[curid][i+1].second-inpos[curid][i].second;
                    aite=inpos[curid][i+1].second-min(dff,inpos[curid][i+1].first-st); break;
                }
                else{
                    ll dff=inpos[curid][i].second-inpos[curid][i+1].second;
                    aite=inpos[curid][i].second-min(dff,st-inpos[curid][i].first); break;
                }
            }
        }
        ll df=abs(b[aite]-a[curid]);
        if(df<=diff)return 1;
        return 0;
    }
    else{
        ll aite=-1;
        for(int i=0;i<outpos[curid].size()-1;i++){
            if(outpos[curid][i].first<=st&&st<=outpos[curid][i+1].first){
                if(outpos[curid][i].first>=pos&&outpos[curid][i+1].first>=pos){
                    ll dff=outpos[curid][i].second-outpos[curid][i+1].second;
                    aite=outpos[curid][i+1].second+min(dff,outpos[curid][i+1].first-st); break;
                }
                else{
                    ll dff=outpos[curid][i+1].second-outpos[curid][i].second;
                    aite=outpos[curid][i].second+min(dff,st-outpos[curid][i].first); break;
                }
            }
        }
        ll df=abs(c[aite]-a[curid]);
        if(df<=diff)return 1;
        return 0;
    }
}
bool remove(DSU& lef, DSU& righ, ll ql, ll qr, bool front){
    if(front){
        ll lst=righ.value(ql);
        if(lst>qr)return 0;
        if(!valid(lst)){
            righ.unite_right(lst,lst+1); lef.unite_left(lst,lst-1); return 1;
        }
        return 0;
    }
    else{
        ll vl=lef.value(qr);
        if(vl<ql)return 0;
        if(!valid(vl)){
            righ.unite_right(vl,vl+1); lef.unite_left(vl,vl-1); return 1;
        }
        return 0;
    }
}
bool ck(ll lambda){
    diff=lambda;
    DSU lef,righ;
    lef.init(n); righ.init(n);
    for(int i=1;i<=2*n;i++){
        curid=i;
        if(i<=n){
            // 1 to i: inside, i+1 to n+1: outside
            if(pos<=i){
                while(remove(lef,righ,1,pos,1));
                while(remove(lef,righ,1,pos,0));
                while(remove(lef,righ,pos,i,1));
                while(remove(lef,righ,pos,i,0));
                while(remove(lef,righ,i+1,n+1,1));
                while(remove(lef,righ,i+1,n+1,0));
            }
            else{
                while(remove(lef,righ,1,i,1));
                while(remove(lef,righ,1,i,0));
                while(remove(lef,righ,i+1,pos,1));
                while(remove(lef,righ,i+1,pos,0));
                while(remove(lef,righ,pos,n+1,1));
                while(remove(lef,righ,pos,n+1,0));
            }
        }
        else{
            // 1 to i-n: outside, i-n+1 to n+1: inside
            if(pos<=i-n){
                while(remove(lef,righ,1,pos,1));
                while(remove(lef,righ,1,pos,0));
                while(remove(lef,righ,pos,i-n,1));
                while(remove(lef,righ,pos,i-n,0));
                while(remove(lef,righ,i-n+1,n+1,1));
                while(remove(lef,righ,i-n+1,n+1,0));
            }
            else{
                while(remove(lef,righ,1,i-n,1));
                while(remove(lef,righ,1,i-n,0));
                while(remove(lef,righ,i-n+1,pos,1));
                while(remove(lef,righ,i-n+1,pos,0));
                while(remove(lef,righ,pos,n+1,1));
                while(remove(lef,righ,pos,n+1,0));
            }
        }
    }
    if(righ.value(1)<=n+1)return 1;
    lef.clear(); righ.clear();
    lef.init(n); righ.init(n);
    for(int i=1;i<=n;i++){
        swap(b[i],c[i]);
    }
    for(int i=1;i<=2*n;i++){
        curid=i;
        if(i<=n){
            // 1 to i: inside, i+1 to n+1: outside
            if(pos<=i){
                while(remove(lef,righ,1,pos,1));
                while(remove(lef,righ,1,pos,0));
                while(remove(lef,righ,pos,i,1));
                while(remove(lef,righ,pos,i,0));
                while(remove(lef,righ,i+1,n+1,1));
                while(remove(lef,righ,i+1,n+1,0));
            }
            else{
                while(remove(lef,righ,1,i,1));
                while(remove(lef,righ,1,i,0));
                while(remove(lef,righ,i+1,pos,1));
                while(remove(lef,righ,i+1,pos,0));
                while(remove(lef,righ,pos,n+1,1));
                while(remove(lef,righ,pos,n+1,0));
            }
        }
        else{
            // 1 to i-n: outside, i-n+1 to n+1: inside
            if(pos<=i-n){
                while(remove(lef,righ,1,pos,1));
                while(remove(lef,righ,1,pos,0));
                while(remove(lef,righ,pos,i-n,1));
                while(remove(lef,righ,pos,i-n,0));
                while(remove(lef,righ,i-n+1,n+1,1));
                while(remove(lef,righ,i-n+1,n+1,0));
            }
            else{
                while(remove(lef,righ,1,i-n,1));
                while(remove(lef,righ,1,i-n,0));
                while(remove(lef,righ,i-n+1,pos,1));
                while(remove(lef,righ,i-n+1,pos,0));
                while(remove(lef,righ,pos,n+1,1));
                while(remove(lef,righ,pos,n+1,0));
            }
        }
    }
    if(righ.value(1)<=n+1)return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    sort(b+1,b+n+1); sort(c+1,c+n+1);
    ll lol=*max_element(a+1,a+2*n+1)-min(*min_element(b+1,b+n+1),*min_element(c+1,c+n+1));
    lol=max(lol,max(*max_element(b+1,b+n+1),*max_element(c+1,c+n+1))-*min_element(a+1,a+2*n+1));
    pos=n+1;
    for(int i=1;i<=n;i++){
        if(a[i]>a[i+n]){
            pos=i; break;
        }
    }
    for(int i=1;i<=2*n;i++)disc.push_back({a[i],i});
    sort(disc.begin(),disc.end());
    SEG ins,outs;
    ins.init(2*n); outs.init(2*n);
    for(int i=1;i<=2*n;i++){
        discval[i]=val({a[i],i});
    }
    for(int i=1;i<=n;i++){
        ins.upd(discval[i],1,2*n,1,1);
        outs.upd(discval[i+n],1,2*n,1,1);
    }
    for(int i=1;i<=n;i++){
        enterin[i]=ins.qry(1,discval[i],1,2*n,1);
        enterout[i+n]=outs.qry(1,discval[i+n],1,2*n,1);
        inpos[i].push_back({1,enterin[i]});
        outpos[i+n].push_back({1,enterout[i+n]});
        if(i==1){
            inpos[i].push_back({1,enterin[i]});
            outpos[i+n].push_back({1,enterout[i+n]});
        }
    }
    for(int i=2;i<=n+1;i++){
        ins.upd(discval[i-1],1,2*n,-1,1);
        ins.upd(discval[i+n-1],1,2*n,1,1);
        outs.upd(discval[i-1],1,2*n,1,1);
        outs.upd(discval[i+n-1],1,2*n,-1,1);
        if(i==pos){
            for(int j=1;j<=2*n;j++){
                bool in=0;
                if(i<=j&&i+n-1>=j)in=1;
                if(in){
                    ll vl=ins.qry(1,discval[j],1,2*n,1);
                    inpos[j].push_back({i,vl});
                }
                else{
                    ll vl=outs.qry(1,discval[j],1,2*n,1);
                    outpos[j].push_back({i,vl});
                }
            }
        }
        enterout[i-1]=outs.qry(1,discval[i-1],1,2*n,1);
        enterin[i+n-1]=ins.qry(1,discval[i+n-1],1,2*n,1);
        inpos[i+n-1].push_back({i,enterin[i+n-1]});
        outpos[i-1].push_back({i,enterout[i-1]});
        inpos[i].push_back({i,ins.qry(1,discval[i],1,2*n,1)});
        outpos[i+n].push_back({i,outs.qry(1,discval[i+n],1,2*n,1)});
    }
    for(int i=1;i<=2*n;i++){
        bool in=0;
        if(i>n)in=1;
        if(in){
            ll vl=ins.qry(1,discval[i],1,2*n,1);
            inpos[i].push_back({n+1,vl});
        }
        else{
            ll vl=outs.qry(1,discval[i],1,2*n,1);
            outpos[i].push_back({n+1,vl});
        }
    }
    for(int i=1;i<=2*n;i++){
        sort(inpos[i].begin(),inpos[i].end());
        sort(outpos[i].begin(),outpos[i].end());
    }
    ll l=0,r=lol;
    while(l<r){
        ll mid=(l+r)>>1;
        if(ck(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33