Submission #1188515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188515		alexdd	Garden (JOI23_garden)	C++20	30 / 100	3114 ms	607484 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];

set<int> s;
multiset<int> rezs;//min(pozs[i]+d - pozs[i+1] + 1)
void baga(int x)
{
    if(s.empty())
    {
        s.insert(x);
        return;
    }
    if(s.find(x) != s.end())
        return;

    s.insert(x);
    auto it = s.find(x);
    if(it == s.begin())
    {
        auto itri = next(it);
        rezs.insert(x+d - (*itri) + 1);
    }
    else if(it == prev(s.end()))
    {
        auto itle = prev(it);
        rezs.insert((*itle)+d - x + 1);
    }
    else
    {
        auto itle = prev(it);
        auto itri = next(it);
        rezs.erase(rezs.find((*itle)+d - (*itri) + 1));
        rezs.insert((*itle)+d - x + 1);
        rezs.insert(x+d - (*itri) + 1);
    }
}

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;
    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;
                }
                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%d])
            {
                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 x:base)
        baga(x);
    set<int> inits=s;
    multiset<int> initrez=rezs;

    for(int jos=d;jos<2*d;jos++)
    {

        s = inits;
        rezs = initrez;

        vector<pair<int,int>> bad;
        for(int x=0;x<m;x++)
        {
            if(special[x].first + d <= jos)
            {
                bad.push_back({special[x].first + d, special[x].second});
            }
            else
            {
                bad.push_back({special[x].first, special[x].second});
            }
        }

        sort(bad.begin(),bad.end());
        int pozbad=0;

        for(int sus=jos-d+1;sus<=goup[jos];sus++)
        {
            while(pozbad < bad.size() && bad[pozbad].first < sus)
            {
                baga(bad[pozbad].second);
                pozbad++;
            }

            int mnm = d;

            if(!rezs.empty()) mnm = min(mnm, *rezs.begin());
            mnm = min(mnm, (*s.rbegin()) - (*s.begin()) + 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: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25