Task :: BubblePosters

Can someone who had solved this task help me. I'm getting MLE on last test case.
My code => http://www.z-trening.com/new/www/html/submit.php?submit=7100051966&subm_code=1
Thanks in advance!

Well I think your idea is good but it won't work cuz of it uses to much memory...

and btw Dgleich, I think you have luck with this task..worst case of your solution is O( n^2 ) which is too much for n = 100 000, so tests are bad.. :)

gates, can you please look in my code and tell me what optimization can I use to solve this task? Thanks

I think so too :D

@FilipKeri: your approach is slow too..maybe you can get ac because tests are bad.

my approach is to sweep through posters and maintain current posters in set.
for every start of poster O( lg N ) complexity to insert poster and for every end of poster O( lg N ) complexity to erase it.
since every poster is inserted and erased exactly once complexity is O( N lg N )

somenone please take a look of my code in http://www.z-trening.com/submit.php?submit=7100065154&subm_code=1

I don't know where my fault is.... Please help!

hmm u first sort all the lenghts and then go throught posters?i have a problem with implementing this with set cause i cant get the biggest number in a set other than in linear time:S|
and i dont feel like making my own BST:D

You can get the biggest element in set like this

set< int , greater<int> > s;

s.insert(1);
s.insert(3);
s.insert(2);

printf( "%d\n" , *s.begin() );

so s.begin points always to the largest element???

Or like this:

set< int > S;
    S.insert ( 1 );
    S.insert ( 3 );
    S.insert ( 2 );
    printf ( "%d\n", *S.end() );   

ok s.begin() points to the smallest and then for s.begin to s.end u get the elements sorted in the ascending order.

Matteo, that's not going to work... Because S.end() isn't really an element, so you need to get *(--S.end()); :)

no u will also get the biggest element that way
even if u increase the iterator like this
it=s.end()
it++
*it will still point to the biggest element

On my computer, it works, because I tried.

I just tryed and it's not working try:
set < int > S;
S.insert( 5 );
S.insert( 4 );
S.insert( 2 );
printf("%d\n",*(--S.end())); //return 5
printf("%d\n",*S.end()); //it returned 3 for me

what compiler are u using??
i have DEV-C++,dont know whats his compiler but it works just fine at my comp:D

I am using gcc 4.4.1...