Submission #1161290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161290		fatman87878	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	37 / 100	4096 ms	12188 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=3e5+5;

int n,a[2][maxN<<1],b[2][maxN],spp[2][maxN<<1],valid[2][maxN];

inline int chk(int guess){
    for(int t:{0,1}){
        fill(valid[0],valid[0]+n+1,0);
        fill(valid[1],valid[1]+n+1,0);
        for(int i = 0;i<n;i++){
            int _l = lower_bound(b[t],b[t]+n,a[0][i]-guess)-b[t]-1;
            int _r = upper_bound(b[t],b[t]+n,a[0][i]+guess)-b[t]-1;
            swap(_l,_r);
            int pos0 = i,l = 0,r = 0;
            if(pos0-_l>spp[0][i])l = n;
            else l = pos0-_l;
            if(pos0-_r<=spp[0][i])r = pos0-_r;
            else r = n;
            l = max(0,l);
            r = max(l,r);
            r = min(i+1,r);
            l = min(l,r);
            valid[0][l]++;
            valid[0][r]--;
            //cout<<l<<' '<<r<<'\n';
        }
        for(int i = n;i<2*n;i++){
            int _l = lower_bound(b[t],b[t]+n,a[0][i]-guess)-b[t];
            int _r = upper_bound(b[t],b[t]+n,a[0][i]+guess)-b[t];
            int pos0 = n-(i-n + min(2*n-i-1,n-spp[0][i]))-1,l = 0,r = 0;
            if(_l-pos0<=0)l = 0;
            else l = min(n,spp[0][i]-1+_l-pos0);
            if(_r-pos0<=0)r = 0;
            else r = min(n+1,spp[0][i]-1+_r-pos0);
            l = max(l,i-n+1);
            r = max(r,l);
            valid[0][l]++;
            valid[0][r]--;
            //cout<<l<<' '<<r<<'\n';
        }
        for(int i = 0;i<n;i++){
            int _l = lower_bound(b[!t],b[!t]+n,a[1][i]-guess)-b[!t];
            int _r = upper_bound(b[!t],b[!t]+n,a[1][i]+guess)-b[!t];
            int pos0 = n-i-1,l = 0,r = 0;
            if(_l-pos0>spp[0][i+n])l = n;
            else l = _l-pos0;
            if(_r-pos0<=spp[0][i+n])r = _r-pos0;
            else r = n+1;
            l = max(0,l);
            r = max(l,r);
            r = min(i+1,r);
            l = min(l,r);
            valid[1][l]++;
            valid[1][r]--;
            //cout<<l<<' '<<r<<'\n';
        }
        for(int i = n;i<2*n;i++){
            int _l = lower_bound(b[!t],b[!t]+n,a[1][i]-guess)-b[!t]-1;
            int _r = upper_bound(b[!t],b[!t]+n,a[1][i]+guess)-b[!t]-1;
            swap(_l,_r);
            int pos0 = i-n + min(i-n+1,n-spp[0][i-n]),l = 0,r = 0;
            //cout<<pos0<<' '<<_l<<' '<<_r<<' ';
            if(pos0-_l<=0)l = 0;
            else l = min(n,spp[0][i-n]-1+pos0-_l);
            if(pos0-_r<=0)r = 0;
            else r = min(n+1,spp[0][i-n]-1+pos0-_r);
            l = max(l,i-n+1);
            r = max(r,i-n+1);
            valid[1][l]++;
            valid[1][r]--;
            //cout<<l<<' '<<r<<'\n';
        }
        for(int i = 0;i<=n;i++){
            valid[0][i+1]+=valid[0][i];
            valid[1][i+1]+=valid[1][i];
            if(valid[0][i]==n&&valid[1][i]==n)return 1;
        }
        //cout<<'\n';
    }
    return 0;
}

int main(){
    IOS
    cin>>n;
    for(int i = 0;i<2*n;i++)cin>>a[0][i],a[1][(i+n)%(2*n)]=a[0][i];
    for(int i:{0,1})for(int j = 0;j<n;j++)cin>>b[i][j];
    sort(b[0],b[0]+n);
    sort(b[1],b[1]+n);
    for(int i = 0;i<n;i++){
        int l = n-1,r = 2*n,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[0][mid]>a[0][i])l = mid;
            else r = mid;
        }
        spp[0][i] = l-n+1;
        //cout<<spp[0][i]<<' ';
    }
    for(int i = n;i<2*n;i++){
        int l = 0,r = n+1,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[0][mid-1]<a[0][i])l = mid;
            else r = mid;
        }
        spp[0][i] = l;
        //cout<<spp[0][i]<<' ';
    }
    //cout<<'\n';
    int l = 0,r = max({*max_element(a[0],a[0]+2*n),*max_element(b[0],b[0]+n),*max_element(b[1],b[1]+n)}),mid;
    for(;l<r;){
        mid = l+r>>1;
        if(chk(mid))r=mid;
        else l = mid+1;
    }
    cout<<l<<'\n';
}

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