JacobianDet's blog

TLE IN SPOJ PATULJCI
By JacobianDet, history, 8 years ago, In English

I tried this problem using segment tree but it's getting TLE. Can anybody explain how to remove TLE from this code?

Solution : https://pastebin.com/8iuk4mQp

Problem : http://www.spoj.com/problems/PATULJCI/

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Well, i don't see why this code should pass. There are simple alternatives than trying to squeeze a heavy-constant segment tree anyway, but if you still want to, you can read. I was able to pass with a Merge Sort Tree in szkopul using some constant optimization, code here. There is a simple solution using the fact that the element appears > 1/2 in the range, we can try to pick random a number between [L,R] and see if in the range, this number appears more than 1/2 times using a histogram, the probability of error is if you try k numbers

→ Reply