Submission #851112

#	Time	Username	Problem	Language	Result	Execution time	Memory
851112		Andrei	Garden (JOI23_garden)	C++17	15 / 100	678 ms	4944 KiB

garden

#include <bits/stdc++.h>

using namespace std;

int n,m,d;

bool ap[10000];

int frx[10000];
int fry[10000];

set <int> h[10000];

queue <int> pos[5000];

int firstOcc[5000];

vector <int> upd[10000];

struct S
{
    int sz=0;
    int prv[10000];
    int nxt[10000];
    int fr[10000]={0};
    int minim=2*d;
    int maxim=-1;
    int ans=0;

    S(vector <pair <int,int>> a)
    {
        sz=(int)a.size()/2;
        for(int i=0; i<2*sz; i++)
        {
            fr[a[i].first]=a[i].second;
            if(i>0)
                nxt[a[i-1].first]=a[i].first;
            if(i+1<2*sz)
            {
                prv[a[i+1].first]=a[i].first;
                ans=max(ans,a[i+1].first-a[i].first-1);
            }
            minim=min(minim,a[i].first);
            maxim=max(maxim,a[i].first);
        }
    }

    void Rem(int x)
    {
        if(sz==1)
        {
            ans=d-1;
            return;
        }

        fr[x]--;
        if(fr[x]>0)
            return;

        if(x>=d)
            sz--;
        if(sz==1)
        {
            ans=d-1;
            return;
        }

        if(x==minim)
        {
            minim=nxt[x];
        }
        else if(x==maxim)
        {
            maxim=prv[x];
        }
        else
        {
            ans=max(ans,nxt[x]-prv[x]-1);
            prv[nxt[x]]=prv[x];
            nxt[prv[x]]=nxt[x];
        }
    }
};

int main()
{
    cin>>n>>m>>d;

    int cntdy=0;
    for(int i=1; i<=n; i++)
    {
        int p,q;
        cin>>p>>q;

        if(frx[p]==0)
            frx[p]++;
        if(frx[p+d]==0)
            frx[p+d]++;

        ap[p]=1;
        ap[p+d]=1;

        if(fry[q]==0)
            cntdy++;
        fry[q]++;
        fry[q+d]++;
    }

    for(int i=1; i<=m; i++)
    {
        int r,s;
        cin>>r>>s;

        if(ap[r]==1 && frx[r]<=1)
            frx[r]++;
        if(ap[r]==0 && frx[r]==0)
            frx[r]++;

        if(ap[r+d]==1 && frx[r+d]<=1)
            frx[r+d]++;
        if(ap[r+d]==0 && frx[r+d]==0)
            frx[r+d]++;

        h[s].insert(r);
        h[s+d].insert(r);
    }

    vector <pair <int,int>> aux;
    for(int i=0; i<2*d; i++)
        if(frx[i]>0)
            aux.push_back(make_pair(i,frx[i]));

    int ans=(int)1e9;
    for(int i=0; i<d; i++)
        firstOcc[i]=-1;
    for(int i=0; i<2*d; i++)
    {
        for(auto it:h[i])
        {
            pos[it].push(i);
            if(pos[it].front()==i)
                firstOcc[it]=i;
            if(pos[it].front()==i-d)
            {
                pos[it].pop();
                firstOcc[it]=pos[it].front();
            }
        }

        for(int j=0; j<2*d; j++)
            upd[j].clear();
        for(int j=0; j<d; j++)
        {
            if(firstOcc[j]>=0)
            {
                upd[firstOcc[j]].push_back(j);
                upd[firstOcc[j]].push_back(j+d);
            }
        }

        S A(aux);

        int cnt=0;
        for(int j=i; j>=0; j--)
        {
            for(int it:upd[j])
                A.Rem(it);

            if(fry[j]>0)
                cnt++;

            if(cnt>=cntdy)
                ans=min(ans,(i-j+1)*(d-A.ans));
        }
    }
    cout<<ans<<"\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25