007 Arbori de intervale

[•mathboy]

Poţi ca în fiecare nod să îţi ţii o structură în care memorezi valoarea şi poziţia elementului din vector. În felul acesta, atunci când alegi maximul pentru fiecare nod, poţi doar să compari cele 2 structuri între ele folosind un operator de comparare.

Sau poţi doar să îţi mai ţii un vector în care memorezi poziţia fiecărui element dintr-un nod şi îl actualizezi în timp ce faci update clasic pe valoarea nodului din arborele de intervale.

[•arvlge]

Puteti sa-mi raspunde-ti la topic al deschis de mine

[•xtreme77]

Implementez eu ceva intr-un mod neoptim, sau la problema asta chiar e imposibil sa iei 100 in Java ?

[•Djok]

Incearca sa construiesti arborele in timp O(N)... poate ajuta

UPD: dar nu cred să ajute..

[•sulzandrei]

Poate ar trebuii modificata limita de timp:
Brute force trebuie sa ia 30-40 dar ia 50 (http://www.infoarena.ro/job_detail/1743886)
Cu intervale de radical(n) trebuie sa ia 50 dar ia 100(http://www.infoarena.ro/job_detail/1743939)

[•mihai.alpha]

WTF imi da 0 puncte cu incorect pe primele 3 teste si TLE pe ultimele 7, insa am verificat Testul 1 (si 2) si raspunsul este exact la fel. ?

Sursa: http://www.infoarena.ro/job_detail/2012947

[•Matteoalexandru]

Salut, nu vreau sa fac reclama la alt site sau ceva dar mi-a fost greu sa inteleg de pe wikipedia, insa pe csacademy arborii de intervale sunt prezentati foarte bine si intr-o maniera interactiva, poate puteti adauga link catre site?
https://csacademy.com/lesson/segment_trees