제출 #1161246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161246		fatman87878	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	3897 ms	14528 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+1;
            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 + n-1-spp[0][i])-1,l = 0,r = 0;
            if(_l-pos0<=0)l = 0;
            else l = min(n,max(0,spp[0][i]-(i-n+1))+_l-pos0);
            if(_r-pos0<=0)r = 0;
            else r = min(n+1,max(0,spp[0][i]-(i-n+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[1][i])l = n;
            else l = _l-pos0;
            if(_r-pos0<=spp[1][i])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 + n-1-spp[1][i],l = 0,r = 0;
            //cout<<pos0<<' '<<_l<<' '<<_r<<' ';
            if(pos0-_l<=0)l = 0;
            else l = min(n,max(0,spp[1][i]-(i-n+1))+pos0-_l);
            if(pos0-_r<=0)r = 0;
            else r = min(n+1,max(0,spp[1][i]-(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,r = n+i,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[0][mid]>a[0][i])l = mid;
            else r = mid;
        }
        if(a[0][l]<=a[0][i])l--;
        spp[0][i] = l-n;
        //cout<<spp[0][i]<<' ';
        // 最後一個嚴格大於的
    }
    for(int i = n;i<2*n;i++){
        int l = i-n+1,r = n+1,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[0][mid]<a[0][i])l = mid;
            else r = mid;
        }
        if(a[0][l]>=a[0][i])l--;
        spp[0][i] = l;
        //cout<<spp[0][i]<<' ';
        //第一個嚴格小於的
    }
    //cout<<'\n';
    for(int i = 0;i<n;i++){
        int l = n,r = i+n+1,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[1][mid-1]<a[1][i])l = mid;
            else r = mid;
        }
        if(a[1][l]>=a[1][i])l--;
        spp[1][i] = l-n;
        //cout<<spp[1][i]<<' ';
        //第一個嚴格小於的
    }
    for(int i = n;i<2*n;i++){
        int l = i-n+1,r = n+1,mid;
        for(;l+1<r;){
            mid=l+r>>1;
            if(a[1][mid]>a[1][i])l =  mid;
            else r = mid;
        }
        if(a[1][l]<=a[1][i])l--;
        spp[1][i] = l;
        //cout<<spp[1][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: 0 / 37
• Subtask 5: 0 / 33