제출 #850914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850914		Andrei	Garden (JOI23_garden)	C++17	0 / 100	265 ms	860 KiB

garden

#include <bits/stdc++.h>

using namespace std;

int n,m,d;

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

vector <int> h[10000];

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 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;
            minim=min(minim,a[i].first%d);
        }
    }

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

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

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

        if(x==minim)
        {
            minim=nxt[x];
            x+=d;
        }

        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;

        frx[p]++;
        frx[p+d]++;

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

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

        frx[r]++;
        frx[r+d]++;

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

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

    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])
            if(firstOcc[it]==-1 || firstOcc[it]==i-d)
                firstOcc[it]=i;

        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: 0 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25