FREQUENT SPOJ....:(

hey was tried solving http://www.spoj.com/problems/FREQUENT/ but “WA” comes up…plz find the bug.or provide any test cases where my code fails…
my solution http://ideone.com/9dNJtd

First of all I would say your implementation is very messy and it remainded me of my early days of programming :stuck_out_tongue:
Mistake in your code is that you are not updating lf and rf in query , correct it and it’ll be accepted

else
{
// You have missed the updates of lf and rf of tree1[node] here

	if(arr[mid]==arr[mid+1])
	tree1[node].mf=max2(tree[p].mf,tree[q].mf,tree1[p].rf+tree1[q].lf);
	else
	tree1[node].mf=max(tree1[p].mf,tree1[q].mf);
//	printf("mama  %d  %d\n",node,tree1[node].mf);
	return node;
}
1 Like

now the TLE comes up…:frowning:
yeah quite new to it…thats why messy…:slight_smile:
btw how much time would it take to be a good one…

could u suggest how to remove TLE in my new code…http://ideone.com/7DvXWv

your logic is correct but your implementation is inefficient
Let me mention few thing

  • tree of size of 4M is enough there is no need to take it 50M
  • There is no need of tree2 at all you could have return stuct node from query
    and I haven’t seen your second code which is gettng TLE but first one after correction should have got accepted.
    try this one http://ideone.com/osSN1C (Its your first code with correction)

seriosly bro was great help…:slight_smile: thnx a lot…:slight_smile:

bt what did u mention abt tree2 i guess u r talking abt tree1 …
could u plzzz show how to retrn stucut node from query in this code or could guide …plzzz…