098 Parcele

[•domino]

Aici puteţi discuta despre problema Parcele.

[u-92]

problema se reduce la aflarea unui interval de lungime D cu suma maxima si nu prea imi dau seama cum sa o rezolv in log(N).. imi poate da cineva o idee?

[ditzone]

Poate te inspira problema atac de la grupa Large runda 12 de la campion:
http://campion.edu.ro/problems.php?mode=view_round&group_number=3&year=2005&round_number=12
Nu-i chiar acelasi lucru, dar e o sursa buna pentru inspiartie

[•filipb]

Daca notezi cu S[k] suma de pe intervalul [k, k+D-1], atunci actualizarea se poate face in O(log N), determinand pentru un interval (x,y) pe Oy ce elemente din vectorul S afecteaza. Query-ul e max(S[1], S[2]...), care se afla in radacina arborelui de intervale.

[u-92]

got it 10x de reply`uri

[•blastoise]

Ma poate ajuta cineva la problema aceasta va rog?
Am incercat sa o rezolv dar nu reusesc.

[•SpiderMan]

Ai la sectiunea Downloads, Lot 2003 ( http://infoarena.ro/downloads#lot ) .

[•blastoise]

De fapt e lot 2003.
M-am uitat pe surse si tot nu am inteles.

[•SpiderMan]

Da, am scris prost. Nu exista explicatii ?

[•blastoise]

Nu sunt explicatii, doar sursele oficiale.