Submission #1177040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177040		dragst	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	629 ms	23924 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long n, a[600005], b[300005], c[300005], l[300005], r[300005], bit[600005], bit2[600005];

bool check(long long x)
{
    long long i, j, jb=1, jb1=1, jc=1, jc1=1, kb=2*n, kb1=2*n, kc=2*n, kc1=2*n;
    for (i=1; i<=2*n+1; i++) {bit[i]=bit2[i]=0;};
    for (i=1; i<=n; i++)
    {
        while (jb<=n+1 && a[jb]<=b[i]+x) {jb++;};
        l[i]=jb-i+1;
        while (kb>n && a[kb]<=b[i]+x) {kb--;};
        r[i]=kb+i-n;
        if (!(kb-jb+1<=n-i || l[i]>r[i] || jb>kb))
        {
            if (kb-jb+1>2*n-i) {bit[1]++;}
            else if (l[i]<1)
            {
                l[i]+=2*n;
                if (l[i]>kb)
                {
                    bit[l[i]]++;
                    bit[1]++;
                    bit[r[i]+1]--;
                };
            }
            else
            {
                bit[l[i]]++;
                bit[r[i]+1]--;
            };
        };
        while (jb1<=n+1 && a[jb1]<b[i]-x) {jb1++;};
        r[i]=jb1-i;
        while (kb1>n && a[kb1]<b[i]-x) {kb1--;};
        l[i]=kb1+i-n+1;
        if (kb1-jb1+1<=2*n-1)
        {
            if (kb1-jb1+1<=n-i || l[i]<=r[i]) {bit[1]++;}
            else if (r[i]<1)
            {
                r[i]+=2*n;
                if (r[i]>kb1)
                {
                    bit[l[i]]++;
                    bit[r[i]+1]--;
                };
            }
            else
            {
                bit[l[i]]++;
                bit[1]++;
                bit[r[i]+1]--;
            };
        };
        while (jc<=n+1 && a[jc]<=c[i]+x) {jc++;};
        l[i]=jc-i+1;
        while (kc>n && a[kc]<=c[i]+x) {kc--;};
        r[i]=kc+i-n;
        if (!(kc-jc+1<=n-i || l[i]>r[i] || jc>kc))
        {
            if (kc-jc+1>2*n-i) {bit2[1]++;}
            else if (l[i]<1)
            {
                l[i]+=2*n;
                if (l[i]>kc)
                {
                    bit2[l[i]]++;
                    bit2[1]++;
                    bit2[r[i]+1]--;
                };
            }
            else
            {
                bit2[l[i]]++;
                bit2[r[i]+1]--;
            };
        };
        while (jc1<=n+1 && a[jc1]<c[i]-x) {jc1++;};
        r[i]=jc1-i;
        while (kc1>n && a[kc1]<c[i]-x) {kc1--;};
        l[i]=kc1+i-n+1;
        if (kc1-jc1+1<=2*n-1)
        {
            if (kc1-jc1+1<=n-i || l[i]<=r[i]) {bit2[1]++;}
            else if (r[i]<1)
            {
                r[i]+=2*n;
                if (r[i]>kc1)
                {
                    bit2[l[i]]++;
                    bit2[r[i]+1]--;
                };
            }
            else
            {
                bit2[l[i]]++;
                bit2[1]++;
                bit2[r[i]+1]--;
            };
        };
    };
    for (i=1; i<=2*n; i++)
    {
        bit[i]+=bit[i-1];
        bit2[i]+=bit2[i-1];
    };
    for (i=1; i<=2*n; i++)
    {
        j=i+n;
        if (j>2*n) {j-=2*n;};
        if (bit[i]==0 && bit2[j]==0) {return true;};
    };
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long i, low=0, high=0, mid;
    cin >> n;
    for (i=1; i<=2*n; i++)
    {
        cin >> a[i];
        high=max(high, a[i]);
    };
    for (i=1; i<=n; i++)
    {
        cin >> b[i];
        high=max(high, b[i]);
    };
    sort(b+1, b+n+1);
    for (i=1; i<=n; i++)
    {
        cin >> c[i];
        high=max(high, c[i]);
    };
    sort(c+1, c+n+1);
    while (low<=high)
    {
        mid=(low+high)/2;
        if (check(mid)) {high=mid-1;}
        else {low=mid+1;};
    };
    cout << low;
}

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