Any hints for this task?Interval(segment) tree or smt else?
z-menadzer
ok i've just realised that this task can be solved by sorting and then going through all intervals inO(n*logn)...
Nah , no sorting , just brute force ...
hmm how?:D
A joj , sry , omasio sam zadatak >.<
Moje resenje - dinamicko u O ( N * Log N )
Nemam sad vremena da ti napisem ideju , kasnije cu ...
Moje resenje - dinamicko u O ( N * Log N )
Nemam sad vremena da ti napisem ideju , kasnije cu ...
:D
pa verovatno ti je ista kao moja...isto O(n*log n)
pa verovatno ti je ista kao moja...isto O(n*log n)
Super ^^
Jel možeš molim te objasnit ideju??
evo na primeru
4 8 5
3 6 7
9 10 3
prvo sortiras ih po pocetku
znaci imas
3 6 7
4 8 5
9 10 3
to ti je O(n*log n)
onda ides kroz sve intervale
prvo ti je suma 0
onda kad dodjes do prvog 3 6 7
ti das sledecem intervalu sumu koja je pre prvog
u ovom slucaju 0 i zamenis ako je ta suma veca od najvece moguce za taj interval
onda suma je 0+7=7 sad trazis binarnom prvi intervala koji se uopste ne preklapa sa 3 6 7
to je 9 10 3 njemu das 0+7=7 vrednost(opet ako je to najveca moguca ovde jeste)
pa ides dalje
sledeci interval ima isto sumu 0 ti to dajes sldecem ali ovde ne menjas jer on vec ima 7
i vrednost 0+5=5
i trazis opet najblizi interval to je 9 10 3 ali tu ne menjas vrednost za njega jer on vec ima 7 od prvog
i onda predjes na zadnji on ima sumu vec 7 i jos 3=10
kod svakog intervala uporedjujes da li je on najveci
prvi ti j3 7
drgi ti je 5
i zadnji je 10
znaci najvise je 10
nadam se da si razumeo nesto:)
4 8 5
3 6 7
9 10 3
prvo sortiras ih po pocetku
znaci imas
3 6 7
4 8 5
9 10 3
to ti je O(n*log n)
onda ides kroz sve intervale
prvo ti je suma 0
onda kad dodjes do prvog 3 6 7
ti das sledecem intervalu sumu koja je pre prvog
u ovom slucaju 0 i zamenis ako je ta suma veca od najvece moguce za taj interval
onda suma je 0+7=7 sad trazis binarnom prvi intervala koji se uopste ne preklapa sa 3 6 7
to je 9 10 3 njemu das 0+7=7 vrednost(opet ako je to najveca moguca ovde jeste)
pa ides dalje
sledeci interval ima isto sumu 0 ti to dajes sldecem ali ovde ne menjas jer on vec ima 7
i vrednost 0+5=5
i trazis opet najblizi interval to je 9 10 3 ali tu ne menjas vrednost za njega jer on vec ima 7 od prvog
i onda predjes na zadnji on ima sumu vec 7 i jos 3=10
kod svakog intervala uporedjujes da li je on najveci
prvi ti j3 7
drgi ti je 5
i zadnji je 10
znaci najvise je 10
nadam se da si razumeo nesto:)