Zadanie

Bude raz jeden dom. V tom dome bude bývať Samko. Keď ho postavia. A za tým domom bude kopec. Ten kopec tam dokonca je už teraz. A je to strmý kopec. A ako to už so strmými kopcami býva, vždy je pri ňom riziko zosuvu pôdy. Samkovi by sa, samozrejme, takýto zosuv nepáčil (keďže by mu mohol poškodiť jeho dom). Preto sa rozhodol (ešte pred stavbou svojho domu) postaviť na svahu niekoľko oporných múrov, ktoré svah spevnia a zosuvom zabránia.

Nechal si urobiť geodetický prieskum kopca, dlho nad ním hútal a nakoniec naplánoval niekoľko múrov. Každý z týchto múrov bude vodorovný – pôjde po vrstevnici. Naplánované múry môžu mať rôzne dĺžky (nemusia byť na celú šírku svahu) a môžu byť v rôznych výškach (na rôznych vrstevniciach).

Plný entuziazmu si Samko naplánoval, v akom poradí jednotlivé múry postaví. Ešte v tom istom záchvate entuziazmu si tento plán nechal schváliť na stavebnom úrade. Neskôr, keď nadšenie trochu opadlo, si však uvedomil, že toto poradie možno nie je najšťastnejšie. Pri stavbe múru v strmom svahu sa vám totiž môže občas stať, že sa vám nejaký ten betónový kváder vymkne spod kontroly a skotúľa sa dolu kopcom. To je už samo o sebe trochu nepríjemné, oveľa horšie však je, ak cestou narazí na nejaký iný, už postavený múr (snáď netreba vysvetľovať prečo).

Samko má už plán stavby schválený na úrade a nemôže sa len tak rozhodnúť, že múry postaví v inom poradí. Môžete mu však aspoň povedať, pri stavbe ktorých múrov hrozí, že by mu uvoľnený kus betónu poškodil nejaký nižšie položený, skôr postavený múr. Pri týchto múroch si potom bude na svoje betónové kvádre dávať špeciálny pozor.

Úloha

Pre účely tejto úlohy si svah budeme predstavovať ako naklonenú rovinu (uhol naklonenia nie je podstatný). Na popisovanie miest na svahu si zavedieme nasledovnú súradnicovú sústavu: vrstevnica tvoriaca úpätie svahu bude \(x\)-ová os a jedna zo spádnic bude \(y\)-ová os, pričom \(y\)-ová súradnica bude rásť s rastúcou nadmorskou výškou. Múry teda budú v našom súradnicovom systéme zodpovedať úsečkám rovnobežným s \(x\)-ovou osou.

Hovoríme, že múr \(A\) ohrozuje múr \(B\), ak je možné z nejakej časti múru \(A\) pustiť kameň tak, aby sa skotúľal a narazil do múru \(B\) (pričom kamene sa kotúľajú po spádniciach). Formálne, múr \(A\) ohrozuje múr \(B\), ak je na vyššej \(y\)-ovej súradnici ako múr \(B\) a ich kolmé projekcie na os \(x\) majú prienik kladnej dĺžky (prienik v jednom bode teda nestačí).

Dostanete popis jednotlivých múrov a poradie, v akom ich Samko bude stavať. O múre \(C\) povieme, že je riskantný, ak existuje nejaký múr \(D\) taký, že \(C\) ohrozuje \(D\), ale múr \(D\) bude postavený skôr než múr \(C\). Pre každý múr rozhodnite, či je riskantný, alebo nie.

Formát vstupu

Prvý riadok vstupu obsahuje jedno celé číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet múrov. Nasleduje \(n\) riadkov, každý z nich popisuje jeden múr. Popis jedného múru sa skladá z troch medzerami oddelených celých čísel \(x_{i,1}\), \(x_{i,2}\), \(y_i\), ktoré znamenajú, že daný múr je úsečka s koncovými bodmi \((x_{i,1},y_i)\) a \((x_{i,2}, y_i)\). Pri každom múre bude pre tieto čísla platiť \(-10^9 \leq x_{i,1} < x_{i,2} \leq 10^9\) a \(0 \leq y_i \leq 10^9\). Navyše platí, že všetky múry sú navzájom disjunktné. Inými slovami, žiadne dva múry nemajú spoločný bod.

Múry si očíslujme \(1, 2, \dots, n\) v poradí, v akom sú uvedené na vstupe. Posledný riadok vstupu obsahuje medzerami oddelené čísla múrov v poradí, v akom ich Samko bude stavať. Každé z čísel \(1, 2, \dots, n\) sa v poslednom riadku vstupu vyskytne práve raz.

Formát výstupu

Pre každý múr (v poradí, ako sú očíslované) vypíšte jeden riadok obsahujúci slovo ANO ak je daný múr riskantný, resp. NIE, ak nie je riskantný.

Príklady

Input:

5
1 6 1
6 9 6
-1 2 4
5 8 3
3 6 4
5 1 3 2 4

Output:

NIE
NIE
ANO
ANO
NIE

Po postavení všetkých múrov bude svah vyzerať nasledovne:

Múry budú postupne pribúdať takto:

Stavba múrov č. 5 a 1 bude bez rizika. Pri stavbe múru č. 3 hrozí poškodenie múru 1. Následná stavba múru č. 2 je opäť bez rizika. Nakoniec, pri stavbe múru 4 hrozí poškodenie múru 1. Riskantné sú teda múry č. 3 a 4.

Naivné riešenie

Jedno možné priamočiare riešenie je postupne simulovať stavanie jednotlivých múrov. Počas simulácie si budeme pamätať zoznam všetkých už postavených múrov. Vždy, keď postavíme nejaký múr \(A\), overíme, či je riskantný. To urobíme jednoducho tak, že pre všetky múry postavené skôr než \(A\) skontrolujeme, či ich \(A\) ohrozuje.

Ostáva ešte doriešiť ako skontrolovať, či múr \(A\) ohrozuje nejaký iný múr \(B\).

Pozícia múru \(M\) je daná trojicou čísel \(x_{M,1}, x_{M,2}, y_M\). Aby sme overili, či nejaký múr \(A\) ohrozuje iný múr \(B\), potrebujeme podľa zadania skontrolovať dve veci:

  1. Či je múr \(A\) na vyššej \(y\)-ovej súradnici než \(B\).
  2. Či sa projekcie múrov na \(x\)-ovú os prekrývajú.

Prvá z týchto podmienok sa dá formálne napísať ako \(y_A > y_B\) a druhá sa dá po kratšom zamyslení napísať ako \(x_{A, 2} > x_{B, 1} \land x_{A, 1} < x_{B, 2}\) (kde \(\land\) znamená logický AND). Obe tieto podmienky vieme teda overiť v konštantnom čase.

Zložitosť

Keď staviame prvý múr, nemusíme kontrolovať nič. Keď staviame druhý, musíme overiť, či neohrozuje ten prvý. Keď staviame tretí, musíme urobiť dve overenia, atď. Dokopy teda budeme robiť \(0 + 1 + 2 + \dots + n-1 = \frac{(n-1)(n)}{2}\) overení, či nejaký múr ohrozuje nejaký iný múr. To nám zaberie \(O(n^2)\) času.

Okrem toho musíme ešte načítať vstup (\(O(n)\) času) a pri stavaní každého múru ho pridať do zoznamu postavených (dokopy tiež \(O(n)\) času). Celková časová zložitosť teda bude \(O(n^2)\).

Pamäťová zložitosť je lineárna: pamätáme si vstup (\(O(n)\) pamäte), zoznam už postavených múrov (tiež \(O(n)\) pamäte) a ešte konštantný počet pomocných premenných.

#include <bits/stdc++.h>
using namespace std;

struct mur {
	int x1, x2, y;
};

bool ohrozuje(mur A, mur B) {// je pravda, ze mur A ohrozuje mur B? 
	return A.y > B.y && A.x1 < B.x2 && A.x2 > B.x1;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<mur> mury(n);
	for(int i=0; i<n; i++) {
		scanf("%d %d %d", &mury[i].x1, &mury[i].x2, &mury[i].y);
	}
	
	vector<int> postaveny;
	vector<bool> riskantny(n); // riskantny[i] = je mur cislo i riskantny?
	for(int i=0; i<n; i++) {
		int d;
		scanf("%d", &d);
		d--;
		riskantny[d] = false;
		for(int j=0; j<postaveny.size(); j++) {
			if(ohrozuje(mury[d], mury[postaveny[j]])) {
				riskantny[d] = true;
				break;
			}
		}
		postaveny.push_back(d);
	}
	
	for(int i=0; i<n; i++) {
		if(riskantny[i])printf("ANO\n");
		else printf("NIE\n");
	}
	return 0;
}

Vzorové riešenie

Podobne ako v predošlom riešení, budeme simulovať stavanie múrov a popri tom kontrolovať, či je práve stavaný múr riskantný. Budeme si však pamätať inú informáciu a kontrolu riskantnosti budeme robiť šikovnejšie.

Os \(x\) (vrstevnicu na úpätí kopca) si môžeme nasekať na kúsky jednotkovej dĺžky. Pre každý takýto dielik sa potom môžeme pýtať otázku:

“Ak sa postavíme na tento dielik a pozrieme sa po spádnici smerom nahor, uvidíme priamo nad nami nejaký múr? Ak áno, ako vysoko bude najnižší takýto múr?”

Keďže všetky súradnice na vstupe sú celočíselné, odpoveď na túto otázku bude v rámci jedného dielika všade rovnaká. Mohli by sme si teda vytvoriť pole, v ktorom by sme si pre jednotlivé dieliky pamätali odpovede na našu otázku (výšku najnižšieho múru nad daným dielikom alebo nekonečno, ak taký múr neexistuje). Samozrejme, nemôžeme si pamätať všetky dieliky na \(x\)-ovej osi (keďže tá je nekonečná). Našťastie, nám budú stačiť iba tie, nad ktorými má šancu byť nejaký múr (čo sú podľa obmedzení zo zadania dieliky ležiace v intervale \([-10^9, 10^9]\)). To, že je to stále trochu veľa (dve miliardy dielikov), vyriešime neskôr.

Na začiatku simulácie sú teda v našom poli samé nekonečná (keďže ešte nič nie je postavené).

Keď staviame múr vo výške \(y\) s \(x\)-ovými súradnicami koncov \(x_1, x_2\), stačí sa nám do nášho poľa pozrieť na dieliky, ktoré ležia v intervale \([x_1, x_2]\). Ak na niektorom z týchto dielikov nájdeme číslo menšie než \(y\), znamená to, že pod múrom, ktorý práve staviame, je už niečo postavené, a teda je riskantný. Ak bude na všetkých dielikoch číslo väčšie než \(y\), potom náš múr nie je riskantný.

Následne ešte musíme naše pole aktualizovať: všetkým dielikom z intervalu \([x_1, x_2]\), ktoré si pamätali číslo väčšie než \(y\) (prípadne nekonečno) zmeníme ich hodnotu na \(y\).

Takto sme sa dopracovali k riešeniu, kde pri stavbe každého múru potrebujeme skontrolovať (a následne aktualizovať) nanajvýš dve miliardy prvkov poľa. To je ešte pomalšie než naivné riešenie, spotrebuje však o to viac pamäte. Dá sa to však zachrániť.

Kompresia súradníc

Najprv vyriešme problém s príliš veľkým poľom. Uvedomme si, že nás v skutočnosti nezaujímajú presné \(x\)-ové súradnice múrov – potrebujeme iba vedieť, ktoré dvojice múrov sa v \(x\)-ovom smere prekrývajú. Na to nám stačí vedieť, v akom poradí budú zaujímavé body (začiatky a konce múrov), ak ich budeme čítať zľava doprava.

Predstavme si, že by sme všetkým múrom zmenili \(x\)-ové súradnice začiatkov aj koncov na nejaké iné, tak, aby sa zachovalo pôvodné poradie, teda aby platilo:

  • Ak bol nejaký bod (začiatok, alebo koniec múru) \(R\) pôvodne naľavo od nejakého iného bodu \(S\), aj v nových súradniciach bude \(R\) naľavo od \(S\).

  • Ak bol bod \(R\) na rovnakej \(x\)-ovej súradnici ako \(S\), aj po novom budú na rovnakej \(x\)-ovej súradnici.

Dostali by sme síce trochu inú situáciu, ale principiálne by vyzerala rovnako – tie isté dvojice múrov by sa prekrývali. To znamená, že aj riskantnosť múrov by bola rovnaká, teda zmenené zadanie by malo rovnaké riešenie, ako to pôvodné.

Presne to aj spravíme. Konkrétne to urobíme tak, aby všetky \(x\)-ové súradnice boli po novom z rozsahu \(0\) až \(2n-1\). To sa určite dá, keďže zaujímavých bodov je presne \(2n\) a niektoré z nich ešte môžu byť na rovnakej \(x\)-ovej súradnici.

Technicky to bude vyzerať tak, že všetky začiatky a konce múrov (vždy s pribaleným číslom daného múru) si spolu utriedime podľa \(x\)-ovej súradnice. Následne ich všetky prejdeme zľava doprava a prečíslujeme (zmeníme im súradnice): doteraz najľavejšia \(x\)-ová súradnica bude odteraz 0, druhá najľavejšia bude 1, a tak ďalej. Pri tom si ešte musíme dávať pozor, aby sme bodom s rovnakou \(x\)-ovou súradnicou dali aj po novom rovnakú. Celá táto maškaráda nám zaberie \(O(n \log n)\) času, keďže musíme triediť (okrem toho robíme už len konštantný počet lineárnych prechodov).

Dostali sme sa do situácie, keď sú všetky \(x\)-ové súradnice z rozumne malého rozsahu, takže namiesto nášho dvojmiliardového poľa nám už stačí iba pole veľkosti \(2n\). S takýmto poľom bude mať náš algoritmus časovú zložitosť \(O(n^2)\), keďže pri stavaní jedného múru potrebujeme skontrolovať nanajvýš \(2n\) prvkov poľa. Pamäťová zložitosť bude \(O(n)\), teda v čase aj pamäti sme sa dostali na úroveň naivného riešenia.

Intervalový strom

Teraz skúsme náš algoritmus zrýchliť. Všimnime si, že v našom poli robíme počas behu algoritmu dva druhy operácií:

  • Nájdi v poli najmenšie číslo s indexom z intervalu \([x_1, x_2)\).
  • Všetky prvky s indexami z intervalu \([x_1, x_2)\), ktoré sú väčšie než \(y\), zmeň na \(y\).

Skúsenejší riešitelia si pravdepodobne spomenú, že na takéto operácie existuje špeciálna dátová štruktúra – intervalový strom. Konkrétne budeme potrebovať minimový intervalový strom s lazy propagation (keďže chceme meniť celý interval naraz). Táto dátová štruktúra dokáže simulovať pole, v ktorom obe uvedené operácie dokáže robiť v logaritmickom čase od počtu prvkov poľa. Ak túto dátovú štruktúru ešte nepoznáte, prečítajte si v našej Kuchárke najskôr o základnom intervalovom strome a potom aj o lazy intervalovom strome.

Zložitosť

Keď namiesto obyčajného poľa použijeme intervalový strom, budeme schopní postaviť jeden múr v čase \(O(\log n)\), keďže pri stavbe múru potrebujeme spracovať iba dve požiadavky do nášho intervalového stromu. Celá simulácia stavby nám teda bude trvať \(O(n \log n)\) času. Kompresia súradníc nám tiež trvala \(O(n \log n)\) času a načítanie vstupu je lineárne, celý algoritmus má teda časovú zložitosť \(O(n \log n)\).

Pamäťová zložitosť bude \(O(n)\), keďže si pamätáme vstup a intervalový strom so zhruba \(2 n\) listami.

#include <bits/stdc++.h>
using namespace std;

const int inf = 1023456789;

struct intervalac
{
	vector<int> strom, lazy;
	vector<int> zac, kon;
	
	intervalac(int sz) {
		int offset;
		for(offset = 1; offset < sz; offset *= 2);
		strom = vector<int>(2*offset, inf);
		kon.resize(2*offset);
		zac.resize(2*offset);
		for(int i=0; i<offset; i++) {
			zac[i+offset] = i;
			kon[i+offset] = i+1;
		}
		for(int i=offset-1; i>0; i--) {
			kon[i] = kon[i*2+1];
			zac[i] = zac[i*2];
		}
		lazy = vector<int>(2*offset, inf);
	}
	
	void nebud_lenivy(int vrchol) {
		if(lazy[vrchol] != inf) {
			for(int i=0; i<2; i++) {
				lazy[vrchol*2+i] = min(lazy[vrchol*2+i], lazy[vrchol]);
				strom[vrchol*2+i] = min(strom[vrchol*2+i], lazy[vrchol]);
			}
			lazy[vrchol] = inf;
		}
	}
	
	int minimum(int a, int b, int vrchol = 1) {
		if(a >= kon[vrchol] || b <= zac[vrchol])return inf;
		if(a <= zac[vrchol] && b >= kon[vrchol])return strom[vrchol];
		nebud_lenivy(vrchol);
		return min(minimum(a,b,vrchol*2), minimum(a, b, vrchol*2+1));
	}
	
	void zmen(int a, int b, int hod, int vrchol = 1) {
		if(a >= kon[vrchol] || b <= zac[vrchol])return;
		if(a <= zac[vrchol] && b >= kon[vrchol]) {
			lazy[vrchol] = min(lazy[vrchol], hod);
			strom[vrchol] = min(strom[vrchol], hod);
			return;
		}
		nebud_lenivy(vrchol);
		zmen(a,b,hod, vrchol*2);
		zmen(a,b,hod, vrchol*2+1);
		strom[vrchol] = min(strom[vrchol*2], strom[vrchol*2+1]);
	}
	
};

struct mur
{
	int x1, x2, y;
	void zmen(int stare_x, int nove_x) {
		if(x1 == stare_x) x1 = nove_x;
		if(x2 == stare_x) x2 = nove_x;
	}
};

int main()
{
	int n;
	scanf("%d", &n);
	vector<mur> mury(n);
	vector<pair<int,int> > podla_x;
	for(int i=0; i<n; i++) {
		scanf("%d %d %d", &mury[i].x1, &mury[i].x2, &mury[i].y);
		podla_x.push_back(make_pair(mury[i].x1, i));
		podla_x.push_back(make_pair(mury[i].x2, i));
	}
	sort(podla_x.begin(), podla_x.end());
	int x = 0;
	for(int i=0; i<podla_x.size(); i++) {
		if(i > 0 && podla_x[i].first > podla_x[i-1].first) x++;
		mury[podla_x[i].second].zmen(podla_x[i].first, x);
	}
	
	intervalac strom(x);
	vector<bool> riskantny(n);
	for(int i=0; i<n; i++) {
		int d;
		scanf("%d", &d);
		d--;
		riskantny[d] = strom.minimum(mury[d].x1, mury[d].x2) < mury[d].y;
		strom.zmen(mury[d].x1, mury[d].x2, mury[d].y);
	}
	
	for(int i=0; i<n; i++) {
		if(riskantny[i])printf("ANO\n");
		else printf("NIE\n");
	}
	
	return 0;
}

Iné riešenie

Iné riešenie, tiež v čase \(O(n \log n)\), dostaneme, ak v predošlom riešení vymeníme úlohy času a \(y\)-ovej súradnice. Múry by sme teda nespracovávali v poradí stavby, ale podľa \(y\)-ovej súradnice od najnižšiehio po najvyšší. V intervalovom strome si potom budeme pamätať odpovede na otázku “Kedy najskôr bude nad týmto dielikom postavený múr?”, pričom vždy berieme do úvahy iba tie múry, ktoré sme už spracovali.

Ešte iné riešenie (doplnil Mišof)

Predstavme si, že kým staviame prvú polovicu múrov, farbíme ich na modro, a keď staviame druhú polovicu múrov, tie už farbíme na červeno. Ak existuje nejaká dvojica múrov, z ktorých druhý ohrozuje prvý, tak sú len tri možnosti: tvoria ju dva modré múry, tvoria ju dva červené múry, alebo nejaký červený múr ohrozuje nejaký modrý múr

Naše nové riešenie bude založené na princípe rozdeľuj a panuj. Spravíme v ňom nasledovné:

  1. Ak máme viac ako jeden modrý múr, rekurzívnym volaním nájdeme všetky riskantné múry medzi modrými múrmi.
  2. Ak máme viac ako jeden červený múr, rekurzívnym volaním nájdeme všetky riskantné múry medzi červenými múrmi (čiže všetky červené múry, ktoré ohrozujú iný, skôr postavený červený múr).
  3. Nejak šikovne pre každý červený múr zistíme, či neohrozuje nejaký modrý.

Ako vieme šikovne spraviť krok 3?

Všetky múry si usporiadame podľa výšky zdola hore. V tomto poradí ich následne spracujeme. Počas spracúvania si udržiavame zjednotenie už spracovaných modrých múrov. Na to nám stačí buď intervalový strom, alebo si napríklad môžeme toto zjednotenie pamätať ako usporiadanú množinu (set) disjunktných intervalov. No a vždy, keď spracúvame červený múr, pozrieme sa, či má neprázdny prienik so zjednotením dovtedy spracovaných modrých.

Akú to má dokopy časovú zložitosť? Podobá sa to tak trochu na MergeSort: tiež robíme dve rekurzívne volania na problém polovičnej veľkosti. MergeSort však navyše spraví len \(O(n)\) práce, zatiaľ čo naše riešenie jej počas zametania v kroku 3 spraví až \(O(n\log n)\). A tento “logaritmus navyše” ostane aj vo výsledku: zatiaľ čo časová zložitosť MergeSortu výjde \(O(n\log n)\), tento náš algoritmus má časovú zložitosť \(O(n\log^2 n)\). Toto riešenie tiež stačilo na plný počet bodov.

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ť.