713 Curent

[•DITzoneC]

Aici puteţi discuta despre problema Curent.

[•pauldb]

In timpul concursului, am primit instiintare ca nu exista zile in care apar si update-uri si query-uri. Cred ca ar trebui completat enuntul problemei.

[•DITzoneC]

Am modificat un pic o restrictie. Cred ca este ok asa.

[•cip]

Legat de aceasta problema...am si eu o mare nedumerire in legatura cu solutia oficiala. In aceasta solutie se face un arbore de intervale pentru Arsi pentru a vedea daca exista sau nu noduri arse pentru fiecare subarbore insa ce nu pricep eu este ce e cu acel "S". Este tot arbore de intervale ? pentru ca daca e tot arbore de intervale, nu pricep cum ai putea pleca de la un nod si actualiza pana la radacina... Desigur foarte simplu este sa parcurgi arborele dintr-un nod in radacina dar astfel nu se obtine log N in cel mai prost caz....poate cineva sa ma lamureasca si pe mine sa dea un detaliu ceva despre acest "S"  ? 


PS: In solutie apare urmatoarea exprimare: ": pentru fiecare interval retinem numarul de noduri accesibile din nodul radacina corespunzator intervalului S[nod](dupa cum am precizat mai sus un interval din secventa este echivalent cu un subarbore din arborele dat la intrare) " .

Daca facem un arbore de intervale obisnuit ( [1...mij....N] ) , nu ai de unde sa stii pentru anumite intervale ce nod radacina au, pentru ca evident pot avea mai multe noduri radacina...

[•mihaionly]

Se pare că nu trec de 35 de puncte din cauza unui "Memory limit exceeded". Am încercat să fac tot felul de optimizări și degeaba..Am înlocuit mergesort-ul cu quciksort, am renunțat la vectorul de tați, la vectorul de vizite ptr. parcurgerea dfs, am reținut arborele ca graf orientat, dar se pare că tot nu e de ajuns.
Probabil problema stă în modul în care țin arborele de intervale. Folosesc o alocare dinamică iar fiecare nod are 2 int-uri și 2 pointeri spre arborii din st și din dreapta.
Mă poate lămuri cineva?

[•Mishu91]

Aloca arborele de intervale static. Dacă îl dai de 4*dimensiunea maximă ar trebui să fie suficient.

[•S7012MY]

Cei care luati incorect pe testul 13 incercati sa mariti dimensiunile vectorilor