1263 Nrsubsecv

[•savim]

Aici puteti discuta despre problema Nrsubsecv.

[•tzipleatud]

Salut! Imi poate zice cineva complexitatea oficiala la aceasta problema? Eu am O(N*logN + M) si iau doar 30 puncte. Multumesc anticipat!

[•a_h1926]

Salut! Eu am facut-o in concurs in O(N+M) si am luat 100. Incearca sa folosesti niste stive pentru a atinge aceasta complexitate. Daca ai nelamuriri, trimite-mi un mesaj si o sa iti raspund .

[•tzipleatud]

Am reusit pana la urma, dupa ce am postat mesajul, sa imi dau seama de solutie! Mersi oricum!

[•ctlin04]

Ce cazuri particulare pot aparea la problema asta, imi da incorect la primele 2 teste grupate si nu inteleg de ce??

[•geniucos]

Eu am avut probleme cu intervalele [0,x] si luam tot 90 in concurs.

[•tzipleatud]

Ce cazuri particulare pot aparea la problema asta, imi da incorect la primele 2 teste grupate si nu inteleg de ce??

Eu am avut probleme cu intervalele [0,x] si luam tot 90 in concurs.

Costin are dreptate, tu ai probleme la intervalele [0,x]. Pune dupa citesti a[ i ]++ si dupa ce citesti x,y pune x++ si y++ si ar trebui sa iei 100. Bafta!

[•ctlin04]

Ms mult, intradevar asta era,    desi nu inteleg de ce sa nu mearga cazul [0,y] daca nu maresc toate valorile cu 1, doar eu am pus ca daca  x==0 sa-mi afiseze rez[y], iar daca nu sa afiseze rez[y]-rez[x-1], unde rez este vectorul cu sume partiale