094 Hotel

[•domino]

Aici puteţi discuta despre problema Hotel.

[•Zeus]

am si eu o intrebare :
solutia oficiala e mai buna de O(logN) pe update si O(1) pe query ?

[•Zeus]

adik luam TLE pe 2, acuma am bagat optimizari la greu si am luat 100.
oricum limita de timp putea fi un pic mai mare

[•bogdan2412]

Limita de timp este chiar foarte mare.  Sursa mea O(logN) pe update + O(1) pe query intra in 0.3 secunde

[•Zeus]

mare jmecher ejti mah tu ....  

[u-92]

eu inca iau 2 TLE`uri si nu mai stiu ce sa optimizez  
am incercat si sa citesc cu fgets (dar merge mai incet   )
am O(1) pe query si O(logN*logN) pe update.. impartirea/inmultirea cu 2 o fac prin shift`ari..

ce optimizari mai pot folosi?   (cum a rulat sursa ta in 0.3? )

[•wefgef]

se poate face in O(1) pe query si O(log n) pe update cu arbori de intervale. intra lejer asa.

[u-92]

mersi.. eu tot cu arbori de intervale am facut.. numai ca la un moment dat cautam binar ceva si calculam suma pe interval, credeam ca e suficient insa se pare ca nu.. o sa ma gandesc cum pot obtine logN

[•Qbyx]

spune cineva si pentru mine cum faceti update in O(logN)? 

[•fireatmyself]

faci un arbore de intervale. pentru fiecare nod ce deserveste intevalul [p.q] vei tine 3 informatii:

1. lungimea celui mai mare interval de camere libere pentru nodul respectiv (l_curr).
2. lungimea celui mai mare interval de camere libere care incepe in p (l_left).
3. lungimea celui mai mare interval de camere libere care se termina in q (l_right).

cand faci update ai 2 cazuri:

1. daca nodul tau este inclus in intervalul pe care faci update, atunci modifici cele 3 valor.
2. daca nodul tau nu este inclus in intervalul pe care faci update, atunci ii modifici valorile in functie de l_curr, l_left si l_right ai fiilor sai. este clar ca poti unii cei doi fii daca exista un interval liber care se termina in capatul din dreapta al fiului stang si un alt interval liber care incepe in capatul stanga al fiului drept.

[•dutzul]

imi poate da cineva un test mic? la downloads nu sunt puse testele. iau doar un test restu WA. mersi anticipat