435 Eliminare

[•astronomy]

Aici puteţi discuta despre problema Eliminare.

[•Dastas]

Cum ar trebui sa fac query-urile in arborele de intervale astfel incat sa tin cont de elementele sterse (notate cu -1)? Mai exact, cum imi dau seama in ce interval trebuie sa fac query?

Am vazut ca solutia oficiala tot asa sterge elementele... dar codul este scris astfel incat nu se poate intelege mare lucru din el

[•astronomy]

Mai tii un arbore pentru asta, care iti va spune care este al K-lea element nescos inca.

[•Dastas]

Si cum as putea face asta?

Eu m-am gandit sa aflu cate elemente au fost eliminate in intervalul [1, x] si [1, y] cu un arbore, si apoi query-ul pt maxim sa-l fac in intervalul [x+eliminate_in1-x, y+eliminate_in1-y]... dar asa si pe cele 2 teste care intra in timp iau WA, deci nu e bine...

[•astronomy]

Sa spunem ca ai un arbore de intervale care pentru un nod care are asociat intervalul [st,dr] stii cate pozitii valide din intervalul [st,dr] ai (pozitii cu elemente neeliminate inca). Acum daca vrei sa stii care este a K-a pozitie valida procedezi in felul urmator: te uiti prima oara la intervalele [1,N/2] si [N/2+1, N], daca in intervalul [1, N/2] ai cel putin K pozitii valide e clar ca pozitia care o cauti se afla in acest interval si este a K-a din acest interval, altfel pozitia care o cauti este a (K-x)-a pozitie din intervalul [N/2+1, N] (unde x este numar de pozitii valide din intervalul [1, N/2]). Procedezi in continuare asa pana restrangi intervalul la un singur element.

[•Dastas]

Ok, mersi, aproape ca mi-a iesit!

Am TLE pe ultimele 2 teste... si am optimizat cat am stiut. Am doua interogari pentru a afla a x-a si a y-a pozitie neeliminata, apoi una pt a afla maximul si apoi o actualizare. Ceva idei de optimizare? In afara de a parsa citirea nu prea mai stiu ce sa fac...

[•pauldb]

Parseaza citirea. Eu asa am ajuns de la 80 la 100.

[•astronomy]

O optimizare care m-a ajutat pe mine a fost sa pun

Cod:

struct elem { int a, b;} A[MAXN];

in loc de

Cod:

int a[MAXN], b[MAXN];

si sa modific simultan arborii, adica fac ceva de genul

Cod:

A[nod].a += valoare1, A[nod].b += valoare2

in functia de update. Banuiesc ca motivul pentru care merge asa mai repede e ca acceseaza mai rapid memoria.

[•Dastas]

  Nu-mi vine sa cred... a intrat in 5.5 sec pe ultimul test 

Puteam sa jur ca folosind structuri va fi cu mult mai incet...

Mersi mult pentru ajutor

[•fireatmyself]

am aceeasi problema ca la elimin (de la preONI). iau SIGSECV si sigur nu este de la memorie. acasa imi merge pe teste mari (10000 de teste random si n-a crapat). ce poate sa fie ? 

http://infoarena.ro/job_detail/85398

[•astronomy]

Ai rulat acasa sub linux sursa?

[•fireatmyself]

n-am linux acasa tre sa vina un hard nou mai incapator si apoi o sa bag linux 

[•marin]

Tinand cont ca elementele sunt cate unu si doua pe linie, cum parsez citirea (ce functie folosesc)?

[•Pepelea_Flaviu]

faci o parsare normala daca ai 2 numere, atunci parcurgi sirul si tot ce e inainte de spatiu pui in a, iar restul in b

[•marin]

Eu inteleg asa:
O sa reduc numarul de accesari la disk cu m/2, unde m este numarul de linii cu cate doua elemente (o sa fac atatea accesari ale diskului cate linii am).
Eu ma intrabam daca pot citi intr-un buffer o data mai multe numere, chiar de pe linii diferite

[•Pepelea_Flaviu]

nu merge....numa sa citesti mai multe numere aflate pe aceasi linie

[•andunhill]

100 de puncte fara parsare  http://infoarena.ro/job_detail/501116

[•toni2007]

http://infoarena.ro/job_detail/275314

Tot fara.

[•vendetta]

i`au decat 70 de pct (cu 3 teste tle ) cu o sursa cu care luam inainte 100 de pct

[•klamathix]

i`au decat 70 de pct (cu 3 teste tle ) cu o sursa cu care luam inainte 100 de pct

Iei fara apostrof sau orice alt separator si iei numai, nu decat. 'Decat' folosesti doar daca verbul are negatie  . Gen 'Nu am decat 50 de sticle de sampanie'.

[•stardust]

Si eu iau tot 70 cu tle pe ultimele 3. Am vazut ca a fost reportata problema pentru limita de timp si e marcata ca rezolvata. Totusi mi se pare destul de stransa. Am vazut ca si tu Razvan folosesti cam tot 28 de mega pe testele alea. Retii si tu 3 informatii pt fiecare nod din arbore ? Ca sa pot sa elimin elementele am nevoie sa tin un arbore care sa imi zica pe ce pozitie in ordinea initiala se afla maximul de pe un interval. Se poate sa scap de arborele asta ?