Brojanje - Hint

Can someone give me a hint for solving task " Brojanje " ? I have tryed using sorting -> http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100034629 and inserting http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100035184 but I get TLE. :\

well, insertion sort with 400 elements ...
because u will have max 400 different elements ...

Ahaaa :) Now I got it. Thanks ;)

np :D

Or you can try with segment or fenwick tree..there limit on number of different elements can be as big as N.

My solution is using interval tree.

interval tree = segment tree = tournament tree :)

you can use cumulative tables and binary search, too ... :D

No trees :P I don't know them. :\ I'll solve it with improved insertion sort ASAP. ^^

@demjan0001:

fenwick tree = cumulative tables;
as i said...and with cumulative tables you can do it in O( lg N ) without additional binary search and additional lg N factor.

i didn't know fenwick tree = cumulative tables ...

now you know...

I have tried but I still get TLE on 2 test cases. :( Can you tell me what's wrong ?

http://www.z-trening.com/new/www/html/submit.php?submit=7100035491&subm_code=1

I've written a similar code in Pascal that couldn't pass first test case because of TLE. Then I just wrote the same one in C++ and it passed. Reading input is faster in C++ and it helps here.

Ok, tnx. ;)

Can anyone tell me what's wrong with my code??

http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100035544

Well, you are using vector::insert, and it has a time complexity of O( n ), and you call it in worst case 100000 times, so its sure you get TLE.

What's wrong now ? :\

http://www.z-trening.com/new/www/html/submit.php?submit=7100035806&subm_code=1

Maybe there is a mistake with your sorting, try to use std::sort.

You can find tests on the top of the page here: http://www.yuoi.nis.edu.rs/takmicenja/2009.1.okr/3.brojanje/task.html

So download them and check them yourself :)

:)

You can also use cumulative tables / fenwick tree without binary search ;) ( O( log n ) query, of course )
( just have a look at my code )