Submission #1113141

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

Main

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;
const int K=1<<21;
const int INF=INT_MAX/2;

int n;
vector<int> a,b,c,pos;
vector<bool> lo;

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();
    }
};

bool check(int k){
    vector<bool> d1(3*n),d2(3*n);
    for(int t=0;t<2;t++){
        int st=0,ed=0;
        Deque q1,q2,q3;
        auto work=[&](int i){
            if(lo[i]){
                // cerr << "LOW\n";
                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{
                // cerr << "HIGH\n";
                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--;
            // cerr << a[i]-k << " " << a[i]+k << " : " << st << " " << ed << "\n";
            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]);;
            // cerr << "PUSH " << pos[i] << "\n";
            // cerr << q1.size() << " " << q2.size() << " " << q3.size() << "\n";
            // cerr << "D : ";
            // for(auto x:q1.dq)cerr << x.second << " ";
            // for(auto x:q2.dq)cerr << x.second << " ";
            // for(auto x:q3.dq)cerr << x.second << " ";
            // cerr << "\n";
            if(i>=n){
                work(i-n);
                // cerr << "POP " << pos[i-n] << "\n";
                // cerr << q1.size() << " " << q2.size() << " " << q3.size() << "\n";
                if(lo[i-n])q2.pop_front();
                else q2.pop_back();
                // cerr << "D : ";
                // for(auto x:q1.dq)cerr << x.second << " ";
                // for(auto x:q2.dq)cerr << x.second << " ";
                // for(auto x:q3.dq)cerr << x.second << " ";
                // cerr << "\n";
                d1[i]=(q1.query()+q2.query()+q3.query()).mx<=0;
            }
        }
        swap(b,c);
        swap(d1,d2);
    }
    for(int i=n;i<2*n;i++){
        if((d1[i]&&d2[i+n])||(d2[i]&&d1[i+n])){
            return true;
        }
    }
    return false;
}

int main(){
    cin >> n;
    a.resize(3*n),b.resize(n),c.resize(n),pos.resize(3*n);
    lo.resize(3*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(auto &x:b){
        cin >> x;
    }
    for(auto &x:c){
        cin >> x;
    }
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    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