Submission #1188563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188563		alexdd	Garden (JOI23_garden)	C++20	75 / 100	3113 ms	737316 KiB

garden

#include <bits/stdc++.h>
using namespace std;
int n,m,d;
vector<int> onpoz[5005][5005];
int poz[500005],cntactive;
bool active[500005];
pair<int,int> special[500005];

int goup[10005],goleft[10005];

int worst[10005];
vector<int> with_worst[10005];

int siz[10005],father[10005];
void init()
{
    for(int i=0;i<=d;i++)
        father[i]=i,siz[i]=1;
}
int gas(int x)
{
    if(father[x]!=x)
        father[x] = gas(father[x]);
    return father[x];
}
void unite(int x, int y)
{
    x = gas(x);
    y = gas(y);
    if(x==y)
        return;
    if(siz[x] < siz[y])
        swap(x,y);
    father[y] = x;
    siz[x] += siz[y];
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>d;
    vector<int> base;
    for(int i=0;i<n;i++)
    {
        int p,q;
        cin>>p>>q;
        onpoz[p][q].push_back(i);
        base.push_back(q);
    }
    for(int i=0;i<m;i++)
    {
        int p,q;
        cin>>p>>q;
        special[i] = {p,q};
    }
    int rez = d*d;
    multiset<int> cv;
    for(int jos=0;jos<2*d;jos++)
    {
        for(int i=0;i<d;i++)
        {
            for(int x:onpoz[jos%d][i])
            {
                if(!active[x])
                {
                    cntactive++;
                    active[x] = 1;
                }
                else
                {
                    cv.erase(cv.find(poz[x]));
                }
                poz[x] = jos;
                cv.insert(poz[x]);
            }
        }
        if(cntactive == n)
        {
            int minlin=jos;
            if(!cv.empty()) minlin = min(minlin, *cv.begin());
            goup[jos] = minlin;
        }
        else
            goup[jos] = -1;
    }

    cv.clear();
    cntactive=0;
    for(int x=0;x<n;x++)
        active[x]=0;
    for(int jos=0;jos<2*d;jos++)
    {
        for(int i=0;i<d;i++)
        {
            for(int x:onpoz[i][jos%d])
            {
                if(!active[x])
                {
                    cntactive++;
                    active[x] = 1;
                }
                else
                {
                    cv.erase(cv.find(poz[x]));
                }
                poz[x] = jos;
                cv.insert(poz[x]);
            }
        }
        if(cntactive == n)
        {
            int minlin=jos;
            if(!cv.empty()) minlin = min(minlin, *cv.begin());
            goleft[jos] = minlin;
        }
        else
            goleft[jos] = -1;
    }


    for(int x:base)
        worst[x] = -1;

    for(int jos=d;jos<2*d;jos++)
    {
        for(int i=0;i<2*d;i++)
            with_worst[i].clear();

        for(int i=0;i<d;i++)
            if(worst[i] != -1)
                worst[i] = jos+1;

        for(int x=0;x<m;x++)
        {
            if(special[x].first + d <= jos)
            {
                worst[special[x].second] = min(worst[special[x].second], special[x].first + d);
            }
            else
            {
                worst[special[x].second] = min(worst[special[x].second], special[x].first);
            }
        }
        for(int i=0;i<d;i++)
            if(worst[i] != -1)
                with_worst[worst[i]].push_back(i);

        init();
        int mxm=0;
        for(int sus=jos+1;sus>=jos-d+1;sus--)
        {
            for(int x:with_worst[sus])
            {
                if(x-1>=0 && worst[x-1] >= sus) unite(x,x-1);
                if(x+1<d && worst[x+1] >= sus) unite(x,x+1);
                mxm = max(mxm, siz[gas(x)]);
            }
            if(sus <= goup[jos])
            {
                rez = min(rez, (jos-sus+1) * (d - mxm));
                int sum=0;
                if(worst[0] >= sus)
                    sum += siz[gas(0)];
                if(worst[d-1] >= sus)
                    sum += siz[gas(d-1)];
                assert(sum < d);
                rez = min(rez, (jos-sus+1) * (d - sum));
            }
        }
    }
    cout<<rez;
    return 0;
}
/*

2 1 5
1 4
2 2
0 0


patratele se repeta din d in d

obs: o sa existe tot timpu o solutie care are fiecare latura <d


*/

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