|
Titlul: 094 Hotel Scris de: Mircea Pasoi din Septembrie 01, 2005, 17:08:43 Aici puteţi discuta despre problema Hotel (http://infoarena.ro/problema/hotel).
Titlul: 094 Hotel Scris de: Catalin Tiseanu din Octombrie 12, 2005, 15:13:36 am si eu o intrebare :
solutia oficiala e mai buna de O(logN) pe update si O(1) pe query ? Titlul: 094 Hotel Scris de: Catalin Tiseanu din Octombrie 12, 2005, 15:20:40 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 :) Titlul: 094 Hotel Scris de: Bogdan-Cristian Tataroiu din Octombrie 12, 2005, 16:01:16 Limita de timp este chiar foarte mare. :? Sursa mea O(logN) pe update + O(1) pe query intra in 0.3 secunde
Titlul: 094 Hotel Scris de: Catalin Tiseanu din Octombrie 12, 2005, 18:41:01 mare jmecher ejti mah tu .... =D>
Titlul: 094 Hotel Scris de: u-92 din Martie 21, 2006, 18:13:32 eu inca iau 2 TLE`uri si nu mai stiu ce sa optimizez :(
am incercat si sa citesc cu fgets (dar merge mai incet :shock: ) 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? :idea: (cum a rulat sursa ta in 0.3? :) ) Titlul: 094 Hotel Scris de: Andrei Grigorean din Martie 21, 2006, 18:17:35 se poate face in O(1) pe query si O(log n) pe update cu arbori de intervale. intra lejer asa.
Titlul: 094 Hotel Scris de: u-92 din Martie 21, 2006, 18:20:36 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
Titlul: Răspuns: 094 Hotel Scris de: Eros Lorand din Aprilie 08, 2008, 21:10:27 spune cineva si pentru mine cum faceti update in O(logN)? :?
Titlul: Răspuns: 094 Hotel Scris de: Bogdan-Alexandru Stoica din Aprilie 08, 2008, 21:50:25 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. Titlul: Răspuns: 094 Hotel Scris de: Bodnariuc Dan Alexandru din Noiembrie 06, 2012, 22:06:59 imi poate da cineva un test mic? la downloads nu sunt puse testele. iau doar un test restu WA. mersi anticipat :D
|