Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Danovi na danoravec@gmail.com

Krtko má rád dážďovky, najlepšie natreté omáčkou. Nemyslite si ale, že to je len tak. Na niektoré časti dážovky sa omáčka proste nehodí. To môže byť spôsobené napríklad nadmerným množstvom povrchového slizu, ktorý je sám o sebe lahodný, s omáčkou je však k ničomu. Krtko je veľmi skúsený dážďovkár, vďaka čomu vie hneď na prvý pohľad povedať, ktoré úseky dážďovky sa oplatí natrieť.

Krtko dážďovky natiera tak, že sa postaví do dostatočnej vzdialenosti, aby dážďovku videl celú. Následne si zapíše pod seba úseky, ktoré treba natrieť. Ako všetci vieme, každá dážďovka sa skladá z \(n\) políčok očíslovaných v poradí od 1 po \(n\). Krtko si teda bude zapisovať úseky \([a, b]\), kde \(a\) je prvé políčko úseku, ktorý chce natrieť a \(b\) je posledné políčko tohoto úseku. Často sa mu však stáva, že počas zapisovania zabudne, že niektoré políčko si už zapísal a tak ho zapíše aj do ďalšieho úseku. Jeho papier teda môže vyzerať tak, že sú na ňom napríklad úseky \([1, 4]\) a \([3, 7]\). Môžeme si všimnúť, že políčka \(3\) a \(4\) sú tu zahrnuté v oboch úsekoch napísaných na papieri a budú teda natreté dvakrát. Toľké plytvanie omáčkou! Uvedomil si to aj sám Krtko a tak vás požiadal, či by ste mu nenapísali program, ktorému ukáže svoj papier a on mu podľa toho nakreslí dážďovku tak, ako má byť natretá.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane Krtkov papier a na výstup nakreslí natretú dážďovku. To znamená, že pre každé políčko dážďovky určí, či má alebo nemá byť natreté. Nezaujíma nás, či niektoré políčko má byť podľa papiera natreté viackrát. Ak má byť natreté aspoň raz, prehlásime ho za natreté, v opačnom prípade za nenatreté.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n\) (\(1 \leq n \leq 10^{6}\)) a \(q\) (\(0 \leq q \leq 10^{5}\)). Číslo \(n\) je počet políčok dážovky, číslo \(q\) je počet úsekov napísaných na Krtkovom papieri.

Nasleduje \(q\) riadkov popisujúcich Krtkov papier. Na každom sú dve celé čísla \(a\), \(b\) (\(1 \leq a \leq b \leq n\)). Tie hovoria, že má byť natretý úsek dážďovky od \(a\)-teho políčka po \(b\)-te vrátane. Úseky na papieri sa môžu ľubovoľne prekrývať. Je teda možné aj to, že niektoré políčka dážďovky budú zahrnuté vo všetkých úsekoch na papieri.

Formát výstupu

Na výstup vypíšte \(n\) medzerou oddelených čísiel. Ako \(i\)-te číslo vypíšte \(0\), ak je \(i\)-te políčko dážďovky nenatreté, v opačnom prípade vypíšte ako \(i\)-te číslo \(1\).

Hodnotenie

Číslo sady 1 2 3 4 5
maximálne \(n\) \(200\) \(20\,000\) \(100\,000\) \(500\,000\) \(1\,000\,000\)
maximálne \(q\) \(100\) \(100\) \(100\,000\) \(100\,000\) \(100\,000\)

Príklady

Input:

8 4
4 7
1 1
3 5
6 7

Output:

1 0 1 1 1 1 1 0

V tejto úlohe sme dostali \(q\) úsekov dážďovky, ktoré máme natrieť omáčkou. Mali sme určiť, ako bude dážďovka vyzerať na konci. Chceli sme teda pre každé políčko dážďovky zistiť, či bude, alebo nebude natreté.

Hrubá sila

Spraviť bruteforce na túto úlohu je pomerne priamočiare. Majme pole dĺžky \(n\) so samými nulami. Nazvime ho d[] a bude reprezentovať, neprekvapivo, dážďovku. Hodnota \(0\) predstavuje nenatreté políčko, hodnota \(1\) bude predstavovať natreté políčko.

Pre každý úsek \([a, b]\) zo vstupu prejdeme všetky políčka v poli d[] od \(a\)-teho po \(b\)-te políčko a na každé z nich nastavíme hodnotu \(1\). To bude znamenať, že je natreté. Na konci nám teda stačí iba vypísať obsah poľa d[].

Každý úsek na vstupe môže mať dĺžku najviac \(n\). Úsekov je \(q\), takže časová zložitosť tohto riešenia je \(O(nq)\). Pamätáme si iba dážďovku, takže pamäťová zložitosť je \(O(n)\).

Lepšie riešenie

Prečo je riešenie hrubou silou také pomalé? Lebo sa veľakrát pozerá na tie isté políčka dážďovky. Možno by sa dalo spraviť to, že dva prekrývajúce sa úseky spojíme do jedného, dlhšieho. Ak takto úseky pospájame, ostanú nám na konci iba neprekrývajúce sa úseky. To znamená, že súčet dĺžok všetkých týchto úsekov bude nanajvýš \(n\).

Ako to ale spraviť efektívne? Povedzme si, že chceme ísť po dážďovke zľava doprava a nikdy sa nechceme vracať na políčka, ktoré sme už prešli. Načítajme si teda najskôr všetky úseky a usporiadajme si ich podľa začiatku. To znamená, že úsek, ktorý začína viac vľavo spracujeme skôr ako ten, ktorý začína viac vpravo. Rovnako ako v riešení hrubou silou, majme pole d[] veľkosti \(n\) so samými nulami.

Zoberme prvý úsek, nazvime ho A, a prejdime všetky políčka dážďovky, ktoré reprezentuje. Každému z týchto políčok v poli d[] nastavíme hodnotu \(1\). Nastavenie hodnoty \(1\) v poli d[] budeme odteraz nazývať natretím políčka dážďovky.

Pozrime sa na druhý úsek v usporiadanom poradí a nazvime ho B. Vieme, že B určite nezačína skôr, ako A, lebo sme ich usporiadali podľa začiatkov. Nastať teda mohol iba jeden z nasledovných prípadov:

  1. B je podúsekom A, teda B začína aj končí skôr ako A
  2. B začína v A a končí neskôr, ako A
  3. B začína neskôr, ako A končí

V prvom prípade môžeme úsek B odignorovať, lebo všetky políčka, ktoré tento úsek zasahuje boli už natreté úsekom A.

V druhom prípade niektoré políčka zo začiatku úseku B už boli natreté úsekom A. Pri natieraní teda stačí pokračovať od konca úseku A až po koniec B.

No a v treťom prípade môžeme natrieť celý úsek B, lebo vieme, že žiadne z jeho políčok doteraz neboli natreté.

Môžeme si všimnúť, že nikdy nepotrebujeme vedieť, kedy začínal naposledy spracovaný úsek. Jediné, čo nás zaujíma je to, ktoré políčko dážďovky sme natreli ako posledné. Stačí nám teda mať jednu premennú, ktorá bude hovoriť, ktoré natreté políčko dážďovky sa nachádza najviac vpravo. Ak teda spracujeme úsek, ktorý končil ďalej, ako bola hodnota tejto premennej v čase jeho spracovania, tak túto premennú nastavíme na koniec tohto úseku.

Máme teda algoritmus, ktorý sa na každé z \(n\) políčok dážďovky pozrie najviac raz. Z toho vyplýva časová zložitosť \(O(n)\). Pozor ale na to, čo robíme s úsekmi. Usporiadavame ich, čo trvá čas \(O(q \log q)\). Naše riešenie má teda zložitosť \(O(n + q \log q)\). Pamäťová zložitosť je \(O(n + q)\), pretože si pamätáme všetky úseky a celú dážďovku.

Všimnime si, že začiatku a konce zadaných úsekov sú z rozsahu od \(1\) po \(n\). Pri triedení čísel s takýmto obmedzením vieme využiť aj rýchlejšie triedenia, napríklad countsort, ktorého zložitosť je \(O(q + n)\). Tým zlepšíme aj celkovú časovú zložitosť na \(O(n + q)\). Ako si však ukážeme o chvíľu, túto zložitosť vieme dosiahnuť aj bez toho, aby sme poznali niektorý z týchto špeciálnych triediacich algoritmov.

Vzorové riešenie

Optimálnu časovú zložitosť sme už síce získali drobným trikom v predchádzajúcom riešení, no poďme sa pozrieť na krajšie a jednoduchšie riešenie, ktoré má dokonca lepšiu pamäťovú zložitosť.

Opäť budeme mať pole dĺžky \(n\), nazvime ho p[]. Tentokrát ale \(i\)-te políčko tohto poľa bude hovoriť, koľko úsekov na tomto políčku začína alebo končí. To znamená, že ak spracúvame úsek [a, b], tak k p[a] pripočítame \(1\) a k p[b + 1] pripočítame \(-1\). Kladné číslo označuje začiatok a záporné koniec. Naviac si všimnite, že koniec je v skutočnosti až jedno políčko za reálnych koncom a to preto, aby sme sme aj toto posledné políčko započítali do zadaného úseku.

Čo teraz môžeme robiť s týmto poľom? Môžeme pre každé políčko zistiť, koľko úsekov ho prekrýva. Majme počítadlo, ktoré hovorí, koľkými úsekmi je prekryté aktuálne políčko. Na začiatku bude mať počítadlo hodnotu \(0\). Teraz prejdime cez všetky políčka poľa p[] zľava doprava. Keď spracúvame \(i\)-te políčko, tak k nášmu počítadlu pripočítame hodnotu p[i]. Ak totiž na \(i\)-tom políčku začínajú nejaké úseky, tak ich počet chceme pripočítať k počítadlu. Ak nejaké úseky končili na políčku \(i-1\), tak ich teraz chceme od počítadla odpočítať.

Navyše, naše pole p[] bez problémov zvláda aj viaceré úseky začínajúce alebo končiace na tom istom políčku. Ak napríklad na pozícii \(a\) začínajú tri rôzne úseky, tak hodnotu p[a] sme zvýšili o 1 trikrát, preto je tam hodnota \(3\). A ak na políčku \(a\) začína úsek a zároveň na políčku \(a-1\) nejaký skončil, tak hodnota p[a] bude rovná 0. To je však v poriadku, pretože 0 znamená, že sa nič nemení.

No a tu už vidíme riešenie. Budeme prechádzať pole p[] a aktualizovať počítadlo úsekov. Ak po aktualizácii počítadla políčkom p[i] bude počítadlo väčšie, ako \(0\), tak vieme, že \(i\)-te políčko je natreté. Ak je počítadlo \(0\), tak je \(i\)-te políčko nenatreté, lebo ho neprekrýva žiaden úsek. Počítadlo určite nikdy nebude menšie, ako \(0\), pretože ak je niekde v poli p[] hodnota \(-1\), tak niekde skôr musí byť jej zodpovedajúca \(+1\).

Pre každý úsek zapíšeme iba dve hodnoty do poľa p[] a toto pole následne raz prejdeme. Výsledná časová zložitosť je teda \(O(q + n)\). Pamätáme si však už len pole p[] (a jednu premennú na počítadlo), preto je pamäťová zložitosť \(O(n)\).

Iné riešenia

Riešení tejto úlohy existuje viac a nespomenieme tu všetky. Za zmienku ale stojí riešenie s neoptimálnou časovou zložitosťou \(O(q \log n)\). Toto riešenie vie natrieť celý úsek v čase \(O(\log n)\). To je veľmi jednoduché, ak na reprezentáciu dážďovky použijeme vhodnú dátovú štruktúru. Najjednoduchšou z možností je asi použiť intervalový strom s lazy propagáciou. Táto dátová štruktúra má široké uplatnenie a ak ju nepoznáte, určite si o nej niečo prečítajte. Keď si o nej už niečo prečítate, vymyslieť toto riešenie bude triviálne a nechávame ho ako cvičenie pre vás.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.