namespace K4{
    constexpr int M=3e4+5;
    struct Chtholly{
        struct seg{
            int l,r;
            mutable int v;
            seg(int a=0,int b=0,int c=0){l=a,r=b,v=c;}
            bool operator < (const seg &b)const{return l<b.l;}
        };
        typedef set<seg>::iterator iter;
        set<seg> s[N];
        inline void init(int n){for(int i=1;i<=n;i++)s[i].clear(),s[i].insert(seg(1,M,0));}
        inline iter split(int id,int pos){
            iter it=s[id].lower_bound(seg(pos,pos,-1));
            if(it!=s[id].end()&&it->l==pos)return it;
            --it;
            int l=it->l,r=it->r,v=it->v;
            if(r<pos)return s[id].end();
            s[id].erase(it);
            s[id].insert(seg(l,pos-1,v));
            return s[id].insert(seg(pos,r,v)).first;
        }
        inline void add(int id,int l,int r,int x){
            iter it2=split(id,r+1),it1=split(id,l);
            for(iter it=it1;it!=it2;++it)it->v+=x;
        }
    }ODT;
    struct Segment_tree{
        int addtag[M<<2],covtag[M<<2],val[M<<2];
        #define ls (p<<1)
        #define rs (p<<1|1)
        #define mid (l+r>>1)
        inline void push_up(int p){val[p]=max(val[ls],val[rs]);}
        inline void update(int p,int k1,int k2){
            if(k1)val[p]=addtag[p]=0,covtag[p]=1;
            val[p]+=k2;
            addtag[p]+=k2;
        }
        inline void push_down(int p){
            update(ls,covtag[p],addtag[p]);
            update(rs,covtag[p],addtag[p]);
            covtag[p]=addtag[p]=0;
        }
        inline void add(int p,int l,int r,int L,int R,int tt){
            if(r<L||l>R)return;
            if(L<=l&&r<=R)return void(update(p,0,tt));
            push_down(p);
            add(ls,l,mid,L,R,tt);
            add(rs,mid+1,r,L,R,tt);
            push_up(p);
        }
        inline void add(int L,int R,int tt){L=max(L,1);R=min(R,M);if(L<=R)add(1,1,M,L,R,tt);}
        #undef ls
        #undef rs
        #undef mid
    }SGT;
    int mx,mn;
    struct point{
        int x,y,color,w;
        bool operator < (const point &b)const{return y<b.y;}
    };
    vector<point> vec;
    inline void rotate(int col){
        int tmp=a[4][col];
        a[4][col]=a[3][col],a[3][col]=a[2][col],a[2][col]=a[1][col],a[1][col]=tmp;
    }
    inline bool check(int minrow,int mid){
        ODT.init(n);
        SGT.update(1,1,0);
        vec.clear();
        int xx=minrow==2?3:2,yy=9-minrow-xx;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=4;j++){
                if(mx-a[1][i]<=mid&&a[minrow][i]-mn<=mid){
                    vec.push_back({a[xx][i],a[yy][i],i,1});
                    vec.push_back({a[xx][i],a[yy][i]+mid+1,i,-1});
                }
                rotate(i);
            }
        }
        sort(vec.begin(),vec.end());
        for(int i=0,j=0;i<vec.size();i=j){
            for(j=i;j<vec.size()&&vec[j].y==vec[i].y;j++){
                point p=vec[j];
                ODT.add(p.color,p.x,p.x+mid,p.w);
                for(auto z:ODT.s[p.color]){
                    // if(p.color==1)cout<<"*"<<y<<' '<<z.l<<' '<<z.r<<' '<<z.v<<endl;
                    if(p.w==1){
                        if(z.v==1&&z.l<=p.x+mid&&p.x<=z.r)
                        SGT.add(max(p.x,z.l),min(p.x+mid,z.r),1);
                    }
                    else{
                        if(z.v==0&&z.l<=p.x+mid&&p.x<=z.r)
                        SGT.add(max(p.x,z.l),min(p.x+mid,z.r),-1);
                    }
                }
            }
            if(SGT.val[1]==n)return 1;
        }
        return 0;
    }
    inline int solve(int minrow){
        int l=0,r=mx-mn,mid,ans=mx-mn;
        while(l<=r){
            mid=l+r>>1;
            // cerr<<l<<' '<<r<<' '<<mid<<' '<<ans<<endl;
            if(check(minrow,mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        return ans;
    }
    inline void GOWORK(){
        mx=-INF,mn=INF;
        for(int i:{1,2,3,4})for(int j=1;j<=n;j++)mx=max(mx,a[i][j]),mn=min(mn,a[i][j]);
        printf("%d\n",min({solve(2),solve(3),solve(4)}));
    }
}

提交记录