Tip na úvod

Aby sme nemuseli špeciálne riešiť začiatok a koniec parkoviska, tak si vieme pridať 2 nabíjacie stanice na začiatok a koniec, ktoré zaberajú celú šírku parkoviska.

Bruteforce

Vytoríme si celé parkovisko ako 2D pole boolovských hodnôt, na začiatku núl, a pre každú nabíjačku zmeníme hodnoty v poli, na všetkých políčkach kam zasahuje z nuly na jednotku.

Na zistenie odpovede prejdeme každý riadok a počítame akú najväčšiu medzeru sme videli.

Časová zložitosť takéhoto riešenia je $O(w(n+l))$, pretože musíme vytvoriť a prejsť pole veľkosti $w\times l$, a pridať $n$ nabíjacích staníc s maximálnou dĺžkou $w$.

Pamäťová zložitosť je $O(wl)$, pretože si musíme pamätať celé pole parkoviska.

Lepší bruteforce

Namiesto vytvárania celého parkoviska si vieme vždy jednoducho zistiť $x$-ové súradnice všetkých nabíjacích staníc, ktoré zasahujú do riadka ktorý aktuálne spracovávame.

To vieme spraviť tak, že si pre každý riadok prejdeme všetky nabíjačky, a zistíme, či cez ne kolobežka na tomto riadku prejde, potom tieto nabíjačky prejdeme v zoradenom poradí podľa $x$, a nájdeme medzi ktorými dvomi je najväčšia medzera.

Časová zložitosť je $O(nw \log n)$, pre každý riadok prejdeme všetky nabíjačky, a tie cez ktoré kolobežka na danom riadku prejde, zoradíme podľa $x$. Všimnime si, že riešenie vieme spraviť aj tak, že si nabíjačky zoradíme podľa $x$ na začiatku, a tak vieme dostať zložitosť $O(nw + n \log n)$, respektíve $O(nw + l)$, ak použijeme counting sort. $^1$

Pamäťová zložitosť je $O(n)$, pretože si musíme pamätať všetky nabíjačky, respektíve $O(n+l)$, ak chceme použiť counting sort.

Zaujímavá myšlienka

Pozrime sa, ako vyzerá $i$-ty riadok v porovnaní s $(i+1)$-vým. Vidíme, že väčšinou vyzerajú celkom podobne a vačšina nabíjačiek zostáva na rovnakých miestach.

Vieme si všimnúť, že ak prechádzame všetky riadky postupne, tak sa nabíjačky dokopy zmenia iba $2n$-krát. Každá nabíjačka sa raz pridá medzi tie aktívne, teda tie, cez ktoré prejde kolobežka na aktuálnom riadku, a raz sa z nich odoberie. Tieto zmeny pre $i$-tu kolobežku nastanú na súradnichiach $y_{0,i}$ a $y_{1,i}$.

Otázkou zostáva, ako tieto zmeny rýchlo vykonávať, a následne rýchlo zisťovať veľkosť najväčšej medzery medzi aktívnymi nabíjačkami.

Optimálne riešenie

Použijeme metódu zametania roviny priamkou. $^2$

Najskôr si vytvoríme zoznam zmien - udalostí. Zmena nastáva na riadku, kde končí alebo začína nejaká nabíjačka. Tieto zmeny si utriedime primárne podľa riadku a sekundárne podľa toho, či sa jedná o začiatok alebo koniec nabíjačky.

Následne zametáme rovinu, teda prechádzame riadky, a držíme si množinu všetkých aktuálne aktívnych nabíjačiek, teda tých cez ktoré prejde kolobežka na aktuálnom riadku - $A$.

Postupujeme následovne: - Na novom riadku prejdeme všetky zmeny, kde sa nám pridá nejaká nabíjačka, a pridáme ich do množiny $A$. - Zistíme, aká je najväčšia medzera medzi 2 aktuálne aktívnymi nabíjačkami. - Vymažeme všetky nabíjačky, ktoré v tomto riadku končia z množiny $A$.

Na uchovávanie si množiny $A$ vieme použiť napríklad std::set v jazyku C++.

Poslednou otázkou zostáva, ako rýchlo sa dá zistiť aká je najväčšia medzera medzi 2 aktívnymi nabíjačkami. To urobíme tak, že si spravíme multimnožinu, teda množinu, ktorá podporuje opakovanie sa prvkov, všetkych veľkostí medzier medzi aktívnymi susediacimi nabíjačkami - $S$. Na to vieme použiť napríklad std::multiset v C++.

Ako robiť zmeny v $S$: - Pri pridaní nabíjačky medzi aktívne sa s medzerami stane to, že sa nejaká medzera, veľkosti $a$, rozdelí na 2 menšie, veľkosti $b,c$. Na to, aby sme vedeli ako vyzerala pôvodná medzera, a ako vyzerajú tie nové potrebujeme vedieť, kde sa nachádza najbližšia nabíjačka na ľavo a na pravo od tej, ktorú sme aktuálne pridali. To vieme spraviť pomocou metód prev/next od práve pridanej nabíjačky v množine $A$.
Potom užiba stačí z $S$ odstrániť $a$ a pridať $b,c$. Je treba dávať si pozor, aby sme pri odstraňovaní nevymazali všetky výskyty medzier veľkosti $a$ z multimnožiny, ale iba jeden.

• Zistíme, aká je najväčšia medzera medzi 2 aktuálne aktívnymi nabíjačkami ako maximum multisetu, teda jeho posledný prvok, pretože multiset je Binárny Vyhľadávací Strom. $^3$

• Pri odobraní nabíjačky sa stane opačná situácia, a dve medzery sa spoja do jednej. Vieme postupovať analogicky ako pri pridávaní, a len vymazať $b,c$ z $S$ a pridať $a$.

Časová zložitosť je $O((n+w) \log n )$, máme $n$ udalostí, ktoré musíme zoradiť $O(n \log n)$, pri každej udalosti hľadáme/vyberáme/pridávame do množiny $O(n \log n)$, a pre každý riadok musíme zistiť aktuálnu veľkosť najväčsej medzery z množiny $S$ - $O(w \log n)$, všimnime si, že taktiež vieme mať zložitosť $O(n \log n + w)$, ak si po každej zmene uchováme aktuálnu najväčšiu dĺžku medzery, namiesto toho, aby sme ju pre každý riadok hľadali v $S$.

Pamäťová zložitosť je $O(n)$, pretože máme $O(n)$ udalostí, a množiny veľkosti $O(n)$.

Riešenie pre iné jazyky

Ak nemáme usporiadanú množinu v štandardnej knižnici, ako to je v C++, tak máme dve možnosti ako si ju implementovať.

• Spravíme si vyvažovaný binárny vyhľadávací strom, na ktorom imlementujeme operácie nasledovný a predchádzajúci prvok $^4$

• Implementujeme množinu pomocou dynamického intervalového stromu nad množinou možných hodnôt - v našom prípade čísla od $0$ do $l$. Zisťovanie nasledovného a predchádzajúceho prvku vieme urobiť pomocou chodenia po intervalovom strome.$^5$

Všimnime si že oboma spôsobmi vieme tak isto implementovať aj multimnožinu.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
#define F first
#define S second
ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,l,w;
    cin>>n>>w>>l;

    vector<vector<int>> events_ytx;
    for (int i=0;i<n;i++){
        int x,a,b;
        cin>>x>>a>>b;

        events_ytx.push_back({a,0,x});
        events_ytx.push_back({b,1,x});
        // Vytváranie eventov
    }

    sort(all(events_ytx));
    events_ytx.push_back({INF,0,0});

    set<int> active={0,l};
    multiset<int> sizes={l}; 
    int c = 0;

    for (int y=0;y<=w;y++){
        while (events_ytx[c][0]<=y && events_ytx[c][1]==0){
            active.insert(events_ytx[c][2]);
            int x1 = events_ytx[c][2];
            int x0 = *prev(active.find(x1));
            int x2 = *next(active.find(x1));
            sizes.erase(sizes.find(x2-x0));
            sizes.insert(x1-x0);
            sizes.insert(x2-x1);
            c++;
        } // Pridanie všetkých začínajúcich nabíjačiek

        cout<<*prev(sizes.end())<<'\n';
        // Vypísanie najväčšej medzery

        while (events_ytx[c][0]<=y && events_ytx[c][1]==1){
            int x1 = events_ytx[c][2];
            int x0 = *prev(active.find(x1));
            int x2 = *next(active.find(x1));
            sizes.erase(sizes.find(x2-x1));
            sizes.erase(sizes.find(x1-x0));
            sizes.insert(x2-x0);
            active.erase(x1);
            c++;
        } // Odobranie všetkych končiacich nabíjačiek
    }
}