Submission #1113147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113147		ttamx	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	30 / 100	5045 ms	56924 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

const int N=3e5+5;
const int INF=INT_MAX/2;

int n;
int a[3*N],b[N],c[N],pos[3*N];
bool lo[3*N],d[3*N];

struct Info{
    int sum,pre,suf,mx;
    static Info unit(){
        return {0,-INF,-INF,-INF};
    }
    friend Info operator+(const Info &l,const Info &r){
        return {l.sum+r.sum,max(l.pre,l.sum+r.pre),max(r.suf,r.sum+l.suf),max({l.mx,r.mx,l.suf+r.pre})};
    }
};

struct Deque{
    using P = pair<Info,int>;
    deque<P> dq;
    vector<Info> l,r;
    void rebalance(bool left){
        int s=dq.size();
        int m=(s+left)/2;
        l.clear(),r.clear();
        {
            Info sum=Info::unit();
            for(int i=m-1;i>=0;i--){
                sum=dq[i].first+sum;
                l.emplace_back(sum);
            }
        }
        {
            Info sum=Info::unit();
            for(int i=m;i<s;i++){
                sum=sum+dq[i].first;
                r.emplace_back(sum);
            }
        }
    }
    bool empty(){return dq.empty();}
    int size(){return dq.size();};
    P front(){return dq.front();}
    P back(){return dq.back();}
    void push_front(Info x,int v){
        dq.emplace_front(x,v);
        if(l.empty())l.emplace_back(x);
        else l.emplace_back(x+l.back());
    }
    void push_back(Info x,int v){
        dq.emplace_back(x,v);
        if(r.empty())r.emplace_back(x);
        else r.emplace_back(r.back()+x);
    }
    void push_front(P x){push_front(x.first,x.second);}
    void push_back(P x){push_back(x.first,x.second);}
    void pop_front(){
        assert(!dq.empty());
        if(l.empty())rebalance(true);
        dq.pop_front();
        l.pop_back();
    }
    void pop_back(){
        assert(!dq.empty());
        if(r.empty())rebalance(false);
        dq.pop_back();
        r.pop_back();
    }
    Info query(){
        if(dq.empty())return Info::unit();
        if(l.empty())return r.back();
        if(r.empty())return l.back();
        return l.back()+r.back();
    }
};

void calc(int *b,bool *d,int k){
    int st=0,ed=0;
    Deque q1,q2,q3;
    auto work=[&](int i){
        if(lo[i]){
            while(!q1.empty()&&q1.back().second>=pos[i]){
                q2.push_front(q1.back());
                q1.pop_back();
            }
            while(!q2.empty()&&q2.front().second<pos[i]){
                q1.push_back(q2.front());
                q2.pop_front();
            }
            while(!q3.empty()&&q3.front().second<pos[i]){
                q1.push_back(q3.front());
                q3.pop_front();
            }
        }else{
            while(!q3.empty()&&q3.front().second<=pos[i]){
                q2.push_back(q3.front());
                q3.pop_front();
            }
            while(!q2.empty()&&q2.back().second>pos[i]){
                q3.push_front(q2.back());
                q2.pop_back();
            }
            while(!q1.empty()&&q1.back().second>pos[i]){
                q3.push_front(q1.back());
                q1.pop_back();
            }
        }
    };
    for(int i=0;i<3*n;i++){
        while(st<n&&b[st]<a[i]-k)st++;
        while(st>0&&b[st-1]>=a[i]-k)st--;
        while(ed<n&&b[ed]<=a[i]+k)ed++;
        while(ed>0&&b[ed-1]>a[i]+k)ed--;
        work(i);
        Info cur{1,1-ed,1+st,1+st-ed};
        if(lo[i])q2.push_front(cur,pos[i]);
        else q2.push_back(cur,pos[i]);
        if(i>=n){
            work(i-n);
            if(lo[i-n])q2.pop_front();
            else q2.pop_back();
            d[i]=(q1.query()+q2.query()+q3.query()).mx<=0;
        }
    }
}

bool check(int k){
    {
        int st=0,ed=0;
        Deque q1,q2,q3;
        auto work=[&](int i){
            if(lo[i]){
                while(!q1.empty()&&q1.back().second>=pos[i]){
                    q2.push_front(q1.back());
                    q1.pop_back();
                }
                while(!q2.empty()&&q2.front().second<pos[i]){
                    q1.push_back(q2.front());
                    q2.pop_front();
                }
                while(!q3.empty()&&q3.front().second<pos[i]){
                    q1.push_back(q3.front());
                    q3.pop_front();
                }
            }else{
                while(!q3.empty()&&q3.front().second<=pos[i]){
                    q2.push_back(q3.front());
                    q3.pop_front();
                }
                while(!q2.empty()&&q2.back().second>pos[i]){
                    q3.push_front(q2.back());
                    q2.pop_back();
                }
                while(!q1.empty()&&q1.back().second>pos[i]){
                    q3.push_front(q1.back());
                    q1.pop_back();
                }
            }
        };
        for(int i=0;i<3*n;i++){
            while(st<n&&b[st]<a[i]-k)st++;
            while(st>0&&b[st-1]>=a[i]-k)st--;
            while(ed<n&&b[ed]<=a[i]+k)ed++;
            while(ed>0&&b[ed-1]>a[i]+k)ed--;
            work(i);
            Info cur{1,1-ed,1+st,1+st-ed};
            if(lo[i])q2.push_front(cur,pos[i]);
            else q2.push_back(cur,pos[i]);
            if(i>=n){
                work(i-n);
                if(lo[i-n])q2.pop_front();
                else q2.pop_back();
                d[i]=(q1.query()+q2.query()+q3.query()).mx<=0;
            }
        }
    }
    {
        int st=0,ed=0;
        Deque q1,q2,q3;
        auto work=[&](int i){
            if(lo[i]){
                while(!q1.empty()&&q1.back().second>=pos[i]){
                    q2.push_front(q1.back());
                    q1.pop_back();
                }
                while(!q2.empty()&&q2.front().second<pos[i]){
                    q1.push_back(q2.front());
                    q2.pop_front();
                }
                while(!q3.empty()&&q3.front().second<pos[i]){
                    q1.push_back(q3.front());
                    q3.pop_front();
                }
            }else{
                while(!q3.empty()&&q3.front().second<=pos[i]){
                    q2.push_back(q3.front());
                    q3.pop_front();
                }
                while(!q2.empty()&&q2.back().second>pos[i]){
                    q3.push_front(q2.back());
                    q2.pop_back();
                }
                while(!q1.empty()&&q1.back().second>pos[i]){
                    q3.push_front(q1.back());
                    q1.pop_back();
                }
            }
        };
        for(int i=0;i<3*n;i++){
            while(st<n&&c[st]<a[i]-k)st++;
            while(st>0&&c[st-1]>=a[i]-k)st--;
            while(ed<n&&c[ed]<=a[i]+k)ed++;
            while(ed>0&&c[ed-1]>a[i]+k)ed--;
            work(i);
            Info cur{1,1-ed,1+st,1+st-ed};
            if(lo[i])q2.push_front(cur,pos[i]);
            else q2.push_back(cur,pos[i]);
            if(i>=n){
                work(i-n);
                if(lo[i-n])q2.pop_front();
                else q2.pop_back();
                if((q1.query()+q2.query()+q3.query()).mx<=0){
                    if(d[i-n]||(i<2*n&&d[i+n])){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    cin >> n;
    vector<pair<int,int>> vals;
    for(int i=0;i<2*n;i++){
        cin >> a[i];
        vals.emplace_back(a[i],i>n?~i:i);
    }
    sort(vals.begin(),vals.end());
    for(int i=0;i<2*n;i++){
        int j=vals[i].second;
        pos[j<0?~j:j]=i;
    }
    for(int i=2*n;i<3*n;i++){
        a[i]=a[i-2*n];
        pos[i]=pos[i-2*n];
    }
    for(int i=0;i<2*n;i++){
        lo[i]=pos[i]<pos[i+n];
    }
    for(int i=2*n;i<3*n;i++){
        lo[i]=lo[i-2*n];
    }
    for(int i=0;i<n;i++){
        cin >> b[i];
    }
    for(int i=0;i<n;i++){
        cin >> c[i];
    }
    sort(b,b+n);
    sort(c,c+n);
    int l=0,r=1'000'000'000;
    while(l<r){
        int m=(l+r)/2;
        if(check(m))r=m;
        else l=m+1;
    }
    cout << l << "\n";
}

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