Ako prvé dĺžím poďakovanie Martinovi “Medvědovi” Marešovi, ktorý preberá všetky zásluhy za tento príklad a jeho (fakt pekné) vzorové riešenie.

Čo so šírkou?

Pozrime sa ako prvé, ako vyriešime problém, ak sme obmedzení šírkou. Toto riešenie nám ukáže pozorovania, ktoré môžeme využiť neskôr.

Pozorovanie: Ak si zafixujeme výšku prvého poschodia, tak sa nám naň oplatí dať čo najviac psíkov, ktorí sa tam zmestia. Zvyšku problému sa potom môžeme venovať tak, že ignorujeme všetkých psíkov, ktorých sme dali na vrchné poschodie.

Prečo? Máme totiž už fixnú výšku to znamená, že ešte zostal kúsok šírky kam sme mohli psíka dať. Ak teda nejakého psíka môžeme dať na prvé poschodie, a dáme ho tam, riešenie to určite nepohorší.

Jedna zradná pasca, do ktorej sa tu riešiteľ môže chytiť je, že jednoducho si povie, že teda napchám všetky búdky, ktoré sa zmestia do šírky na prvé poschodie, tým ho vyhlásim za hotové a už sa venujem iba zvyšku.

Tento algoritmus by fungoval asi tak, že iteruje cez búdky, a ak sa aktuálny psík zmestí na aktuálne “rozrobené” poschodie, pridám ho naň. Ak sa však nezmestí, vyhlásim poschodie za hotové, pripočítam jeho výšku k priebežnému výsledku, a začnem znova s novým poschodím.

To však nefunguje, viď protipríklad:

`3
sirka
5
4 2
1 8
4 9`

Správna odpoveď by totiž bola $11$, ale vyššie spomínaný “pažravý program” by vyhlásil, že riešenie je $17$.

Problém je, že náš postup funguje pre fixnú výšku poschodia. Popísaný pažravý algoritmus však nastaví výšku tak aby sa využila celá šírka poschodia, čo vôbec nemusí viesť k optimálnemu riešeniu.

Dynamika

Táto pasca sa dá obísť tak, že si všimneme, čo sme vlastne pri pozorovaní zistili. Chceme si oddeliť časť psíkov, a pre zvyšok vyrátať najnižšiu výšku, do ktorej ich môžeme dať.

Myšlienka je taká, že si pre každého psíka spočítame, koľko výšky by potrebovali na ubytovanie všetci psíkovia po neho. Hlavne je potrebné si uvedomiť, že ak už takýto domček postavíme, tento psík bude posledný na poslednom poschodí, a teda značí nejakú hranicu nového poschodia.

Na tejto myšlienke postavme algoritmus. Pre každého psíka sa budeme snažiť vyrátať hodnotu $MH$ (ako minimal height). $MH[i]$ bude značiť, koľko najmenej výšky musíme použiť, aby sme ubytovali prvých $i$ psíkov. Toto nám dáva základ pre dynamické programovanie - budeme hodnoty $MH$ rátať postupne z predošlých hodnôt.

Ako vyrátam stav v dynamike?

Všimnime si, že hodnota $MH[i]$ závisí iba na prvých $i-1$ psíkoch (podľa toho ako sme si to zadefinovali). Predstavme si teda, že už máme vypočítané optimálne hodnoty $MH[0]$ až $MH[i-1]$. Ako vypočítame hodnotu $MH[i]$?

Myšlienka bude takáto: Keďže psíkovia môžu značiť aj “hranicu”, kde začína nové poschodie, tak si pre $i$-tého psíka jednoducho pozrieme, koľko výšky by spotrebovalo, keby predošlé poschodie končilo na nejakom z predošlých psíkov.

Pre každý index $j: j \leq i$ si “odsimulujeme” nasledovné: Chceli by sme, aby všetci psíkovia od psíka $j$ po psíka $i$ bývali spolu na poschodí. Môžu sa tam nezmestiť (poschodie nie je dosť široké), vtedy nerobíme nič.

Ale ak sa tam náhodou zmestia, tak by sme vedeli pre prvých $i$ psíkov skonštruovať domček vysoký $MH[j-1] + maxh([j,i])$, pričom teda $maxh([j,i])$ značí maximálnu výšku psíka na intervale $[j,i]$. Toto značenie budem používať aj pre zvyšok príkladu.

Prečo? Z dynamiky vieme, že domček pre prvých $j-1$ psíkov bude vysoký $MH[j-1]$, a pridáme k tomu najnižšie možné poschodie, do ktorého sa určite zmestí aj najväčší psík na intervale $[j,i]$.

A tak máme jednu potenciálnu hodnotu pre číslo $MH[i]$. Ak toto spravíme pre každý index $j: j \leq i$, tak určite nájdeme optimálne riešenie pre $MH[i]$, pretože v optimálnom riešení musí byť nejaký psík prvým na tom istom poschodí, na ktorom je psík $i$ posledný.

Časová zložitosť

Pre výpočet hodnoty $MH[i]$ musíme skontrolovať všetky $j: j \leq i$. Napríklad si vieme priebežne udržiavať najväčšieho psíka, ktorého sme doteraz videli, a taktiež šírku aktuálneho intervalu. Na vypočítanie jednej $MH$ hodnoty teda stačí jeden prechod poľa psíkov – časová zložitosť $O(n)$. To nám dáva celkovú časovú zložitosť $O(n^2)$.

Obmedzenie na výšku pomocou

šírky

Už vieme pre nejakú zadanú šírku $x$ zistiť, aký najnižší panelák s takou výškou vieme postaviť. Zároveň však vieme pozorovať, že pre ľubovoľnú šírku väčšiu ako $x$ bude najnižší panelák s takou výškou nižší (alebo rovnako veľký), a opačne, ľubovoľný užší panelák bude aspoň tak vysoký.

Vieme teda binárne vyhľadať najmenšiu šírku, pre ktorú bude najnižší panelák nižší ako naše obmedzenie (teda sa zmestí). Jednoducho si zvolíme nejakú strednú hodnotu (ako šírku), vypočítame pre ňu najnižšiu možnú výšku.

Ak sa zmestí pod naše obmedzenie, tak vieme, že všetky širšie domy nie sú optimálne široké. Ak sa naopak nezmestí pod naše obmedzenie, tak môžeme zahodiť všetky rovnaké a menšie hodnoty.

Toto nás teda dostane na časovú zložitosť $O(n^2 * \log H)$.

Pekná myšlienka do budúcna

Skúsme však spraviť riešenie, ktoré bude závisieť iba od počtu psíkov.

Pozorovanie: optimálna šírka bude určite určená nejakým súvislým úsekom psíkov, ktorí budú spolu na poschodí.

V optimálnom riešení musí byť aspoň na jednom poschodí úplne plno (teda nikde neostane voľné miesto). Ak by totiž ostalo na každom poschodí trošku miesta, môžeme jednoducho zmenšiť optimálne riešenie (čo je teda spor).

Všimnime si taktiež, že súvislých úsekov psíkov je omnoho menej ako $H$ - iba $n^2$. Vieme si teda všetky tieto súvislé úseky psíkov vyrobiť, utriediť, a binárne vyhľadávať iba na týchto hodnotách.

Výroba týchto úsekov bude trvať $O(n^2)$, utriedenie $O(n^2 \log n^2)$, čo je asymptoticky $O(n^2 \log n)$. Toto nám časovú zložitosť zrazí až na $O(n^2 \log n)$, čo je vzorová časová zložitosť pre sady $1-5$.

Áno, cez testovač prešli aj časové zložitosti závislé od $H$, ale myšlienka určenia optimálneho riešenia pomocou súvislého úseku psíkov sa nám bude hodiť neskôr, a je fajn sa s ňou pohrať najprv takto.

Zrýchlenie

funkcie na výpočtu najnižšej výšky

Časť algoritmu, ktorá nás aktuálne najviac obmedzuje, je funkcia výpočtu najmenšej výšky pre zadanú šírku. Poďme sa teda na ňu pozrieť a skúsiť ju zrýchliť.

Rátame pre každé $i$, $MH[i]$ ako minimálnu hodnotu z výrazov $MH[j-1] + maxh([j, i])$, pre každé $j \leq i$.

Pozorovanie 1: Pre zafixovaný index $i$, a zmenšujúci sa index $j$ sa hodnota $maxh([j,i])$ zvyšuje, alebo ostáva rovnaká.

Jednoducho na čím dlhší interval (smerom doľava od $i$) sa pozeráme, maximum, ktoré sme videli sa určite nezmenší.

Pozorovanie 2: Ak sa práve pozeráme na interval po i, tak pre každé j platí, že $maxh([j,i])$ je rovné prvému prvku na indexe väčšom ako j takému, že doprava nemá žiadny väčší prvok.

To nejak intuitívne dáva zmysel, lebo tento prvok nemá nič väčšie doprava, a ak by existoval prvok na j,i, ktorý by bol väčší ako tento, tak by tiež nemal nič väčšie doprava, a bol by bližšie ku indexu j.

To dáva prvú myšlienku tohto algoritmu: urobiť si z psíkov postupne dátovú štruktúru, v ktorej bude postupnosť prvkov, ktoré pre daný interval (od $0$ po nejaké $i$) nemajú smerom doprava žiadny vyšší prvok, pričom udržiavame ich poradie v pôvodnej postupnosti.

Napríklad pre postupnosť: $5,4,5,8,6,7,5,2,3$ by táto dátová štruktúra vyzerala asi takto: $8,7,5,3$.

Všimnime si, že z definície je táto dátová štruktúra utriedená, lebo klesá, a tiež indexy stúpajú. Toto sa volá invariant a takáto dátová štruktúra sa vo všeobecnosti volá monotonický stack - skrátene monostack. Monotónniu sme už overili, vieme že klesá a neskôr ukážeme, že sa táto štruktúra naozaj chová ako stack

Pozorovanie 3: Všimnime si, že pre monostack skonštruovaný po index $i$ a pre nejaký index $j$ platí, že $maxh([j,i])$ je rovné prvku monostacku, ktorý sa vyskytol na najbližšom vyššom indexe od $j$. Totiž podľa vlastnosti monostacku vieme, že smerom doprava žiadnu väčšiu hodnotu nemá, no a doľava tiež nie (na intervale $[j,i]$), lebo inak by táto väčšia hodnota patrila do monostacku (nemala by doprava väčšiu hodnotu).

To nám však dáva kľúčovú vlastnosť pre zrýchlenie algoritmu: Ak máme dve po sebe idúce prvky monostacku, jeden s výskytom na indexe $u$ a hodnotou $t$, druhým s výskytom na indexe $q, (q > u)$ s hodnotou $m$, tak pre interval $[u,q]$ existuje nejaké $j: u < j \leq q$, také že $maxh([j,i]) = m$. Slovne: vieme si prejdený interval rozdeliť na niekoľko podintervalov, pre ktoré je hodnota $maxh([j,i])$ určená najbližším prvkom v monostacku. Predstavte si tú hodnotu $maxh([j,i])$, ktorú ku pole dynamického programovania $MH$ pridávame, ako nejaké schody.

Volajme prvok, ktorý je v monostacku ako “obmedzujúci” pre interval, kde určuje ten $maxh$.

Intervaláč ráta dynamiku

Konečne sa však dostávame ku kľúčovej myšlienke zrýchlenia: budeme si hodnoty $MH[j-1] + maxh([j,i])$ udržiavať v minimovom intervalovom strome. Dáva to zmysel - celý čas hľadáme iba nejaké minimum z nejakých prvkov.

Toto nám zaručí, že hodnotu $MH[i]$ vieme zistiť v čase $O(\log n)$, stačí nám totiž vedieť, (podobne ako pri pomalšom riešení), ktorý najpravejší psík sa nám ešte zmestí na to isté poschodie ako ten aktuálny (psík $i$). Označme tohoto najpravejšieho $r$.

Potom sa vieme jednoducho opýtať na minimum z intervalu $[r,i-1]$, čo bude optimálna hodnota $MH[i]$.

Ako však updatnuť celý intervaláč, aby sme rovnako rýchlo vedeli zistiť optimálnu hodnotu pre $MH[i+1]$?

Ako prechádzať medzi

výpočtami?

Vyzbrojení našimi pozorovaniami, pridajme psíka $i$ do monostacku. Stane sa jedna z dvoch vecí: 1) Psík je nižší ako predošlý psík v monostacku. Vtedy nemusíme robiť skoro nič, lebo pre všetky $j$ sú $maxh([j,i+1])$ rovnaké ako pre $maxh([j,i])$. Jediná výnimka je interval $[i,i]$, kde predtým nič nebolo. Teraz je tam nový psík, ktorý je nový najvyšší na tomto intervale. Stačí teda updatnuť tento interval so psíkom, ktorý práve pribudol. Vyzeralo by to tak, že pôvodne by na $i$-tom indexe v intervaláči bola hodnota $MH[i]$ (lebo napravo od tejto pozície nebol žiaden psík), a teraz by sme tam uložili $MH[i] + vyska[i]$. 2) Psík je vyšší ako niektoré psíky v monostacku. To však znamená, že na niektorých intervaloch sa zvýši $maxh([j,i+1])$ oproti $maxh([j,i])$. My však presne podľa pozorovania vieme, ktoré intervaly to sú! Ak je psík vyšší ako nejaký prvok v monostacku, my presne vieme o koľko, a pre ktorý interval bol tento prvok v monostacku obmedzujúci. Stačí teda každú hodnotu v tomto intervale navýšiť o rozdiel medzi novým psíkom a starým (čo pomocou lazy intervaláču hravo zvládneme v $O(\log n)$).

Rekapitulácia algoritmu

Udržujeme si monostack, kde sú práve tí psíkovia, ktorí nemajú žiadneho väčšieho psíka napravo pre aktuálny interval: $0$ až nejaké $i$.

Každý z týchto psíkov je obmedzujúcim pre nejaký interval hodnôt - to znamená, že pre ľubovoľné číslo $j$ patriace do tohoto intervalu bude $maxh([j,i]) =$ veľkosť obmedzujúceho psíka.

V intervalovom strome si na pozícii $p \leq i$ pamätáme nasledovné: $MH[p] + maxh([p,i])$. $MH[i]$ vypočítame ako minimum z nejakého intervalu (toho intervalu, ktorý sa ešte zmestí do danej šírky).

Ak potom chceme posunúť $i$, tak musíme updatnuť monostack pridaním nového psíka. Tento psík sa stane novým obmedzujúcim psíkom pre každý interval, ktorého aktuálny obmedzujúci psík je menší ako tento.

Druhý sčítanec ($maxh([p,i])$) teda pre tieto intervaly lazy updatneme o rozdiel medzi aktuálnym a minulým obmedzujúcim psíkom.

Pfuh. Akú má toto celé časovú zložitosť?

Pre každý prvok urobíme operáciu zistenie minima z nejakého intervalu na intervaláči, čo nás stojí $O(\log n)$.

Tiež však robíme nejaké range update operácie na našom intervaláči. Koľko ich bude?

Jednu musíme spraviť práve vtedy, keď pridávame nového psíka do monostacku a keď odstraňujeme nového psíka z monostacku. A keďže každého psíka môžeme pridať a odstrániť len raz, dokopy to spravíme najviac $2n$ krát, teda nás to celé bude stáť $O(n \log n)$.

Myšlienka z minula

No dobre. Tak teraz vieme pomocou tejto novej vylepšenej funkcie v čase $O(n \log n)$ nájsť najnižší domček s obmedzenou šírkou.

Čo ak sme však obmedzení výškou?

Vždy vieme spraviť rovnakú vec ako minule a binárne vyhľadať šírku, pre ktorú je najnižší domček s touto šírkou nižší ako obmedzenie.

Teda, vieme jednoducho vyriešiť príklad v $O(n \log n \log H)$.

To však nie je optimálna zložitosť, závislá iba od $n$. Keď sa však pokúsime aplikovať myšlienku s generovaním a utriedením všetkých súvislých intervalov (aby sme dostali plný počet za teoretické), zistíme, že generovanie týchto intervalov nám pôvodne trvalo $O(n^2 \log n)$, takže by sme si novou zrýchlenou funkciou vlastne vôbec nepomohli.

My však vieme tento postup ešte stále zrýchliť.

Priemerne dobré binárne

vyhľadávanie

Hlavná myšlienka tejto optimalizácie je nasledovná: pri binárnom vyhľadávaní je síce optimálne vždy vyberať ako pivot prvok “v strede”, ale aj pri výbere rovnomerne náhodného prvku ako pivota je časová zložitosť priemerne logaritmická.

Keď na utriedenom poli binárne vyhľadávame, stačí, že vyberieme náhodný prvok a podľa neho zahodíme alebo si ponecháme zvyšné prvky. Nerozdelíme vždy pole na polovicu, ale priemer počtu “zahodených” prvkov ostane rovnaký.

Prečo nás toto však zaujíma? My si totiž súvislé úseky psíkov nemusíme generovať - my si iba môžeme pamätať, že existujú.

Pre každého psíka $i$ si pamätajme nasledovný interval: ak by poschodie s psíkom $i$ na začiatku určovalo šírku paneláku, psíky v tomto intervale by mohli byť tie posledné na tomto poschodí.

Pre každého psíka $i$ si jednoducho pamätáme množinu psíkov, ktorí môžu byť pravou stranou súvislého úseku psíkov, ktorí určuje šírku paneláku. Táto množina bude súvislý úsek.

A keďže je táto množina súvislý úsek, môžeme si ju pamätať pomocou dvoch čísel - pravého a ľavého konca. Volajme tento interval množina pravých (Kubov) koncov.

Keď si takto kompaktne pamätáme všetky súvislé úseky, ktoré ešte môžu určovať šírku paneláku, rovnomerne náhodne z nich jeden vyberieme.

Zistíme, či je panelák takejto šírky možný alebo nie. Pre každého psíka potom upravíme množinu pravých koncov podľa výsledku. Možno na prvý pohľad nie je jasné, ako by sme to mali robiť, ale v skutočnosti stačí pole psíkov prejsť pomocou dvoch bežcov. A môžeme opakovať.

Akú má celé toto časovú zložitosť? Tak funkcia “zisti pre zadanú šírku najnižšiu výšku paneláku” nás stojí $O(n \log n)$, vybrať rovnomerne náhodný úsek zvládneme tiež v $O(n)$, a podľa výsledku updatnuť množinu pravých koncov pre každého psíka nás tiež stojí $O(n)$. Dokopy túto celú procedúru budeme volať v priemere $O(\log n)$ krát, čo nám dá finálnu časovú zložitosť $O(n \log^2 n)$.

#include <iostream>
#include <vector>
#include <string>
#include <random>

using namespace std;
vector<long long> pref_sums;

long long psum(int l, int r) {
    return pref_sums[r+1] - pref_sums[l];
}

mt19937_64 mt;
long long mt_range(long long lo, long long hi) { return lo + mt() % (hi - lo + 1); }

struct Intervalac
{
    public:
    vector<long long> tree;
    vector<long long> lazy_update;
    int offset;

    Intervalac(vector<long long> pole){
        int next2 = 1;
        while (next2 < pole.size())
        {
            next2 *=2;
        }

        offset = next2;
        next2 *=2;
        tree.resize(next2);

        for (int i = 0; i < pole.size(); i++)
        {
            tree[i+offset] = pole[i];
        }

        for (int i = offset-1; i > 0; i--)
        {
            tree[i] = min(tree[i*2], tree[i*2+1]);
        }
        lazy_update.resize(next2);
    }

    long long mr(int l, int r, int dl, int dr, int vtx) {
        if (lazy_update[vtx] != 0)
        {
            tree[vtx] += lazy_update[vtx];
            if (vtx*2 < tree.size())
            {
                lazy_update[vtx*2] += lazy_update[vtx];
                lazy_update[vtx*2+1] += lazy_update[vtx];
            }
            lazy_update[vtx] = 0;
        }

        if (dl <= l && r <= dr)
        {
            return tree[vtx];
        }

        if (dr < l || r < dl)
        {
            return 1e17;
        }

        int mid = (l+r)/2;
        long long out = min(
            mr(l,mid,dl,dr,vtx*2),
            mr(mid+1,r,dl,dr,vtx*2+1)
        );

        if (vtx*2 < tree.size())
        {
            tree[vtx] = min(tree[vtx*2], tree[vtx*2+1]);
        }
        return out;
    }

    long long min_range(int l, int r) {
        return mr(0, offset-1, l, r, 1);
    }

    void ur(int l, int r, int dl, int dr, int vtx, long long val) {
        if (dl <= l && r <= dr)
        {
            lazy_update[vtx] += val;
        }

        if (lazy_update[vtx] != 0)
        {
            tree[vtx] += lazy_update[vtx];
            if (vtx*2 < tree.size())
            {
                lazy_update[vtx*2] += lazy_update[vtx];
                lazy_update[vtx*2+1] += lazy_update[vtx];
            }
            lazy_update[vtx] = 0;
        }

        if (dl <= l && r <= dr)
        {
            return;
        }

        if (dr < l || r < dl)
        {
            return;
        }

        int mid = (l+r)/2;

        ur(l,mid,dl,dr,vtx*2, val);
        ur(mid+1,r,dl,dr,vtx*2+1, val);

        if (vtx*2 < tree.size())
        {
            tree[vtx] = min(tree[vtx*2], tree[vtx*2+1]);
        }      
    }

    void update_range(int l, int r, long long val) {
        ur(0, offset-1, l, r, 1, val);
    }

};

long long min_height(vector <pair<long long, long long>> &psiky, long long wid) {
    int n = psiky.size();
    vector<long long> init(n+1,0);

    int l = 0; int r = 0;
    vector<pair<long long, pair<int,int>>> monostack;
    monostack.push_back({0,{0,0}});
    Intervalac intervalac = Intervalac(init);
    long long curr_wid = 0;

    for (int i = 0; i < n; i++)
    {
        r++;
        long long curr_top = psiky[r-1].second;
        curr_wid += psiky[r-1].first;

        int interval = r;
        int x = monostack.size();
        for (int g = 0; g < x; g++)
        {
            long long porovnavam = monostack.back().first;
            if (porovnavam < curr_top)
            {
                long long diff = curr_top - porovnavam;
                intervalac.update_range(monostack.back().second.first, monostack.back().second.second, diff);
                interval = monostack.back().second.first;
                monostack.pop_back();
            } else
            {
                break;
            }
        }
        monostack.push_back({curr_top,{interval,r-1}});
        monostack.push_back({0,{r,r}});

        while (curr_wid > wid)
        {
            curr_wid-= psiky[l].first;
            l++;            
        }

        intervalac.update_range(r,r, intervalac.min_range(l, r-1));
    }

    return intervalac.tree[intervalac.offset+n];
}

void update_intervals(vector<pair<long long, long long>> &psiky, vector<pair<int,int>> &konce, bool vacsie, long long sol) {
    int n = psiky.size();

    int l = 0;
    bool found = false;
    for (int i = 0; i < n; i++)
    {
        long long wid = psum(l,i);
        if (vacsie)
        {
            if (wid <= sol)
            {
                konce[l] = {max(konce[l].first, i+1), konce[l].second};
            } else
            {
                while (psum(l,i) > sol)
                {
                    konce[l] = {max(konce[l].first, i), konce[l].second};
                    l++;
                }
                konce[l] = {max(konce[l].first, i+1), konce[l].second};
            }

            if (i == n-1)
            {
                while (l < i)
                {
                    l++;
                    konce[l] = {konce[l].second, konce[l].second};
                }
            }

        } else
        {
            if (found)
            {
                while (psum(l,i) >= sol)
                {
                    konce[l] = {konce[l].first, min(i, konce[l].second)};
                    l++;
                }
            } else
            {
                while (true)
                {
                    long long widd = psum(l,i);
                    if (widd == sol)
                    {
                        found = true;
                        break;
                    } else if (widd > sol)
                    {
                        konce[l] = {konce[l].first, min(i, konce[l].second)};
                        l++;
                    } else
                    {
                        break;
                    }
                }
            }
        }   
    }
}

int main() {
    int n; cin >> n;
    string typ; cin >> typ;
    long long obmedzenie; cin >> obmedzenie;
    vector <pair<long long, long long>> psiky(n);
    for (int i = 0; i < n; i++)
    {
        cin >> psiky[i].first;
        cin >> psiky[i].second;
    }


    if (typ == "sirka")
    {
        cout << min_height(psiky, obmedzenie) << endl;
        return 0;
    }

    pref_sums.resize(n+1,0);
    long long mini = 0;
    for (int i = 0; i < n; i++)
    {
        pref_sums[i+1] = pref_sums[i]+psiky[i].first;
        mini = max(mini, psiky[i].first);
    }

    vector<pair<int,int>> jakub_konce(n);

    for (int i = 0; i < n; i++)
    {
        jakub_konce[i] = {i,n};
    }

    update_intervals(psiky,jakub_konce,true, mini-1);
    vector<int> pmoz(n,0);
    while (true)
    {
        long long moznosti = 0;
        pmoz.resize(n,0);

        for (int i = 0; i < n; i++)
        {
            pmoz[i] = jakub_konce[i].second - jakub_konce[i].first;
            if (pmoz[i] < 0)
            {
                pmoz[i] = 0;
            }
            moznosti += pmoz[i];

        }

        if (moznosti == 1)
        {
            break;
        }

        long long nahodna = mt_range(0,moznosti-1);

        long long wid = 0;
        for (int i = 0; i < n; i++)
        {
            if (nahodna - pmoz[i] < 0)
            {
                wid = psum(i,jakub_konce[i].first+nahodna);
                break;
            }
            nahodna -= pmoz[i];
        }

        long long sol = min_height(psiky, wid);

        if (sol > obmedzenie)
        {
            update_intervals(psiky, jakub_konce, true, wid);
        } else
        {
            update_intervals(psiky, jakub_konce, false, wid);
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (pmoz[i])
        {
            cout << psum(i,jakub_konce[i].first) << endl;
            return 0;
        }
    }
}