Submission #1159328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159328		tosivanmak	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	5134 ms	942976 KiB

Main

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

struct Pers{
    vector<ll>seg,lc,rc;
    ll cur=1;
    ll n;
    void init(ll _n){
        n=_n; seg.push_back(0); lc.push_back(0); rc.push_back(0);
    }
    ll create(){
        seg.push_back(0); lc.push_back(0); rc.push_back(0);
        cur++; return cur-1;
    }
    ll build(ll l, ll r){
        if(l==r){
            ll nid=create(); return nid;
        }
        ll mid=(l+r)>>1;
        ll nid=create();
        lc[nid]=build(l,mid); rc[nid]=build(mid+1,r);
        return nid;
    }
    ll upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            ll nid=create();
            seg[nid]=seg[id]+val; return nid;
        }
        ll nid=create();
        ll mid=(l+r)>>1;
        if(ul<=mid){lc[nid]=upd(ul,l,mid,val,lc[id]); rc[nid]=rc[id];}
        else{rc[nid]=upd(ul,mid+1,r,val,rc[id]); lc[nid]=lc[id];}
        seg[nid]=seg[lc[nid]]+seg[rc[nid]];
        return nid;
    }
    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,lc[id])+qry(ql,qr,mid+1,r,rc[id]);
    }
    ll bs(ll l, ll r, ll k, ll id){
        if(l==r)return l;
        ll mid=(l+r)>>1;
        if(seg[lc[id]]>=k)return bs(l,mid,k,lc[id]);
        else return bs(mid+1,r,k-seg[lc[id]],rc[id]);
    }
    ll kth(ll k, ll ver){
        return bs(1,n,k,ver);
    }
}ins,outs;
ll a[600005],b[300005],c[300005];
ll verin[300005],verout[300005];
ll discval[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=ins.qry(1,discval[curid],1,2*n,verin[st]);
        ll df=abs(b[aite]-a[curid]);
        if(df<=diff)return 1;
        return 0;
    }
    else{
        ll aite=outs.qry(1,discval[curid],1,2*n,verout[st]);
        ll df=abs(c[aite]-a[curid]);
        if(df<=diff)return 1;
        return 0;
    }
}
bool remove(set<ll>& st, ll ql, ll qr, bool front){
    if(!st.size())return 0;
    ll lst=*st.rbegin(); ll bgn=*st.begin();
    if(lst<ql)return 0;
    if(bgn>qr)return 0;
    if(front){
        lst=*st.lower_bound(ql);
        if(lst>qr)return 0;
        if(!valid(lst)){
            st.erase(st.find(lst)); return 1;
        }
        return 0;
    }
    else{
        auto it=st.upper_bound(qr); it=prev(it);
        ll vl=*it;
        if(vl<=ql)return 0;
        if(!valid(vl)){
            st.erase(st.find(vl)); return 1;
        }
        return 0;
    }
}
bool ck(ll lambda){
    diff=lambda;
    set<ll>st;
    for(int i=1;i<=n+1;i++)st.insert(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(st,1,pos,1));
                while(remove(st,1,pos,0));
                while(remove(st,pos,i,1));
                while(remove(st,pos,i,0));
                while(remove(st,i+1,n+1,1));
                while(remove(st,i+1,n+1,0));
            }
            else{
                while(remove(st,1,i,1));
                while(remove(st,1,i,0));
                while(remove(st,i+1,pos,1));
                while(remove(st,i+1,pos,0));
                while(remove(st,pos,n+1,1));
                while(remove(st,pos,n+1,0));
            }
        }
        else{
            // 1 to i-n: outside, i-n+1 to n+1: inside
            if(pos<=i-n){
                while(remove(st,1,pos,1));
                while(remove(st,1,pos,0));
                while(remove(st,pos,i-n,1));
                while(remove(st,pos,i-n,0));
                while(remove(st,i-n+1,n+1,1));
                while(remove(st,i-n+1,n+1,0));
            }
            else{
                while(remove(st,1,i-n,1));
                while(remove(st,1,i-n,0));
                while(remove(st,i-n+1,pos,1));
                while(remove(st,i-n+1,pos,0));
                while(remove(st,pos,n+1,1));
                while(remove(st,pos,n+1,0));
            }
        }
    }
    if(st.size())return 1;
    for(int i=1;i<=n+1;i++)st.insert(i);
    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(st,1,pos,1));
                while(remove(st,1,pos,0));
                while(remove(st,pos,i,1));
                while(remove(st,pos,i,0));
                while(remove(st,i+1,n+1,1));
                while(remove(st,i+1,n+1,0));
            }
            else{
                while(remove(st,1,i,1));
                while(remove(st,1,i,0));
                while(remove(st,i+1,pos,1));
                while(remove(st,i+1,pos,0));
                while(remove(st,pos,n+1,1));
                while(remove(st,pos,n+1,0));
            }
        }
        else{
            // 1 to i-n: outside, i-n+1 to n+1: inside
            if(pos<=i-n){
                while(remove(st,1,pos,1));
                while(remove(st,1,pos,0));
                while(remove(st,pos,i-n,1));
                while(remove(st,pos,i-n,0));
                while(remove(st,i-n+1,n+1,1));
                while(remove(st,i-n+1,n+1,0));
            }
            else{
                while(remove(st,1,i-n,1));
                while(remove(st,1,i-n,0));
                while(remove(st,i-n+1,pos,1));
                while(remove(st,i-n+1,pos,0));
                while(remove(st,pos,n+1,1));
                while(remove(st,pos,n+1,0));
            }
        }
    }
    if(st.size())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+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+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<=n;i++)disc.push_back({a[i],i});
    sort(disc.begin(),disc.end());
    ins.init(disc.size()); outs.init(disc.size());
    verin[0]=ins.build(1,disc.size()); verout[0]=outs.build(1,disc.size());
    verin[1]=verin[0]; verout[1]=verout[0];
    for(int i=1;i<=n;i++){
        verin[1]=ins.upd(val({a[i],i}),1,2*n,1,verin[1]);
        verout[1]=outs.upd(val({a[i+n],i+n}),1,2*n,1,verout[1]);
    }
    for(int i=2;i<=n+1;i++){
        verin[i]=ins.upd(val({a[i-1],i-1}),1,2*n,-1,verin[i-1]);
        verin[i]=ins.upd(val({a[i+n-1],i+n-1}),1,2*n,1,verin[i]);
        verout[i]=outs.upd(val({a[i-1],i-1}),1,2*n,1,verout[i-1]);
        verout[i]=outs.upd(val({a[i+n-1],i+n-1}),1,2*n,-1,verout[i]);
    }
    for(int i=1;i<=2*n;i++){
        discval[i]=val({a[i],i});
    }
    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: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33