Submission #1176692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176692		dragst	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	694 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];

void add(long long x, long long y)
{
    while (x<=2*n)
    {
        bit[x]+=y;
        x+=(x&(-x));
    };
}

long long sum(long long x)
{
    long long ans=0;
    while (x>0)
    {
        ans+=bit[x];
        x-=(x&(-x));
    };
    return ans;
}

void add2(long long x, long long y)
{
    while (x<=2*n)
    {
        bit2[x]+=y;
        x+=(x&(-x));
    };
}

long long sum2(long long x)
{
    long long ans=0;
    while (x>0)
    {
        ans+=bit2[x];
        x-=(x&(-x));
    };
    return ans;
}

bool check(long long x)
{
    long long i, j=1, k=2*n;
    for (i=1; i<=2*n; i++) {bit[i]=bit2[i]=0;};
    for (i=1; i<=n; i++)
    {
        while (j<=n+1 && a[j]<=b[i]+x) {j++;};
        l[i]=j-i+1;
        while (k>n && a[k]<=b[i]+x) {k--;};
        r[i]=k+i-n;
        if (l[i]>r[i]) {continue;}
        else if (l[i]<1)
        {
            l[i]+=2*n;
            if (l[i]<=k) {continue;}
            else
            {
                add(l[i], 1);
                add(1, 1);
                add(r[i]+1, -1);
            };
        }
        else
        {
            add(l[i], 1);
            add(r[i]+1, -1);
        };
    };
    j=1; k=2*n;
    for (i=1; i<=n; i++)
    {
        while (j<=n+1 && a[j]<b[i]-x) {j++;};
        r[i]=j-i;
        while (k>n && a[k]<b[i]-x) {k--;};
        l[i]=k+i-n+1;
        if (l[i]<=r[i]) {add(1, 1);}
        else if (r[i]<1)
        {
            r[i]+=2*n;
            if (r[i]<=k) {continue;}
            else
            {
                add(l[i], 1);
                add(r[i]+1, -1);
            };
        }
        else
        {
            add(l[i], 1);
            add(1, 1);
            add(r[i]+1, -1);
        };
    };
    j=1; k=2*n;
    for (i=1; i<=n; i++)
    {
        while (j<=n+1 && a[j]<=c[i]+x) {j++;};
        l[i]=j-i+1;
        while (k>n && a[k]<=c[i]+x) {k--;};
        r[i]=k+i-n;
        if (l[i]>r[i]) {continue;}
        else if (l[i]<1)
        {
            l[i]+=2*n;
            if (l[i]<=k) {continue;}
            else
            {
                add2(l[i], 1);
                add2(1, 1);
                add2(r[i]+1, -1);
            };
        }
        else
        {
            add2(l[i], 1);
            add2(r[i]+1, -1);
        };
    };
    j=1; k=2*n;
    for (i=1; i<=n; i++)
    {
        while (j<=n+1 && a[j]<c[i]-x) {j++;};
        r[i]=j-i;
        while (k>n && a[k]<c[i]-x) {k--;};
        l[i]=k+i-n+1;
        if (l[i]<=r[i]) {add2(1, 1);}
        else if (r[i]<1)
        {
            r[i]+=2*n;
            if (r[i]<=k) {continue;}
            else
            {
                add2(l[i], 1);
                add2(r[i]+1, -1);
            };
        }
        else
        {
            add2(l[i], 1);
            add2(1, 1);
            add2(r[i]+1, -1);
        };
    };
    for (i=1; i<=2*n; i++)
    {
        j=i+n;
        if (j>2*n) {j-=2*n;};
        if (sum(i)==0 && sum2(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];
    };
    sort(b+1, b+n+1);
    for (i=1; i<=n; i++)
    {
        cin >> 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: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33