Submission #1113135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113135		ttamx	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	30 / 100	5044 ms	69304 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;
int a[3*N],b[N],c[N];
int pos[3*N];
int l[3*N],r[3*N];
bool d1[3*N],d2[3*N];

struct Info{
    int sum,pre,suf,mx;
    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 SegTree{
    Info t[K];
    void build(int l,int r,int i){
        t[i]={0,-INF,-INF,-INF};
        if(l==r)return;
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
    }
    void build(){
        build(1,2*n,1);
    }
    void modify(int l,int r,int i,int x,Info v){
        if(l==r)return void(t[i]=v);
        int m=(l+r)/2;
        if(x<=m)modify(l,m,i*2,x,v);
        else modify(m+1,r,i*2+1,x,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void modify(int x,Info v){
        modify(1,2*n,1,x,v);
    }
    bool query(){
        return t[1].mx<=0;
    }
}seg;

bool check(int k){
    for(int i=1;i<=2*n;i++){
        l[i]=lower_bound(b+1,b+n+1,a[i]-k)-b-1;
        r[i]=upper_bound(b+1,b+n+1,a[i]+k)-b-1;
    }
    for(int i=2*n+1;i<=3*n;i++){
        l[i]=l[i-2*n];
        r[i]=r[i-2*n];
    }
    seg.build();
    for(int i=1;i<=n;i++){
        seg.modify(pos[i],{1,1-r[i],1+l[i],1+l[i]-r[i]});
    }
    for(int i=n+1;i<=3*n;i++){
        seg.modify(pos[i-n],{0,-INF,-INF,-INF});
        seg.modify(pos[i],{1,1-r[i],1+l[i],1+l[i]-r[i]});
        d1[i]=seg.query();
    }
    for(int i=1;i<=2*n;i++){
        l[i]=lower_bound(c+1,c+n+1,a[i]-k)-c-1;
        r[i]=upper_bound(c+1,c+n+1,a[i]+k)-c-1;
    }
    for(int i=2*n+1;i<=3*n;i++){
        l[i]=l[i-2*n];
        r[i]=r[i-2*n];
    }
    seg.build();
    for(int i=1;i<=n;i++){
        seg.modify(pos[i],{1,1-r[i],1+l[i],1+l[i]-r[i]});
    }
    for(int i=n+1;i<=3*n;i++){
        seg.modify(pos[i-n],{0,-INF,-INF,-INF});
        seg.modify(pos[i],{1,1-r[i],1+l[i],1+l[i]-r[i]});
        d2[i]=seg.query();
    }
    for(int i=n+1;i<=2*n;i++){
        if((d1[i]&&d2[i+n])||(d2[i]&&d1[i+n])){
            return true;
        }
    }
    return false;
}

int main(){
    cin >> n;
    vector<pair<int,int>> vals;
    for(int i=1;i<=2*n;i++){
        cin >> a[i];
        vals.emplace_back(a[i],i);
    }
    sort(vals.begin(),vals.end());
    for(int i=0;i<2*n;i++){
        pos[vals[i].second]=i+1;
    }
    for(int i=2*n+1;i<=3*n;i++){
        a[i]=a[i-2*n];
        pos[i]=pos[i-2*n];
    }
    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);
    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