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 ;)
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 ...
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.
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 )
