Submission #1188484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188484		alexdd	Garden (JOI23_garden)	C++20	0 / 100	3117 ms	596320 KiB

garden

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

int goup[10005],goleft[10005];

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

    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}])
            {
                if(!active[x])
                {
                    cntactive++;
                    active[x] = 1;
                }
                poz[x] = jos;
            }
        }
        if(cntactive == n)
        {
            int minlin=jos;
            for(int x=0;x<n;x++)
                minlin = min(minlin, poz[x]);
            goleft[jos] = minlin;
        }
        else
            goleft[jos] = -1;
    }

    for(int jos=d;jos<2*d;jos++)
    {
        for(int sus=jos-d+1;sus<=goup[jos];sus++)
        {
            vector<int> pozs;
            for(int x=0;x<m;x++)
            {
                if((sus <= special[x].first && special[x].first <= jos) || (sus <= special[x].first + d && special[x].first + d <= jos))
                {

                }
                else
                {
                    pozs.push_back(special[x].second);
                }
            }
            int mnm = d;

            /*for(int dr=d;dr<2*d;dr++)
            {
                int minx=dr;
                for(int x:pozs)
                {
                    if(x+d <= dr)
                        minx = min(minx, x+d);
                    else
                        minx = min(minx, x);
                }
                mnm = min(mnm, dr - min(minx,goleft[dr]) + 1);
            }*/

            if(pozs.empty())
            {
                for(int dr=d;dr<2*d;dr++)
                    mnm = min(mnm, dr - goleft[dr] + 1);
            }
            else
            {
                sort(pozs.begin(),pozs.end());
                pozs.erase(unique(pozs.begin(),pozs.end()), pozs.end());

                /*for(int dr=d;dr<pozs[0]+d;dr++)
                {
                    int minx=dr;
                    for(int x:pozs)
                    {
                        if(x+d <= dr)
                            minx = min(minx, x+d);
                        else
                            minx = min(minx, x);
                    }
                    mnm = min(mnm, dr - min(minx,goleft[dr]) + 1);
                }*/

                for(int i=0;i+1<pozs.size();i++)
                {
                    mnm = min(mnm, pozs[i]+d - min(goleft[pozs[i]+d], pozs[i+1]) + 1);
                    if(goleft[pozs[i]+d] < pozs[i+1])
                    {
                        for(int dr=pozs[i]+d+1;dr<pozs[i+1]+d;dr++)
                        {
                            if(goleft[dr] >= pozs[i+1])
                            {
                                mnm = min(mnm, dr - pozs[i+1] + 1);
                                break;
                            }
                            mnm = min(mnm, dr - goleft[dr] + 1);
                        }
                    }
                }

                mnm = min(mnm, pozs.back()+d - min(goleft[pozs.back()+d], pozs[0]+d) + 1);
                if(goleft[pozs.back()+d] < pozs[0]+d)
                {
                    for(int dr=pozs.back()+d+1;dr<2*d;dr++)
                    {
                        if(goleft[dr] >= pozs[0]+d)
                        {
                            mnm = min(mnm, dr - (pozs[0]+d) + 1);
                            break;
                        }
                        mnm = min(mnm, dr - goleft[dr] + 1);
                    }
                }
            }
            rez = min(rez, (jos-sus+1) * mnm);
        }
    }
    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: 0 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25