 # SPOJ ANDROUND TLE

getting TLE even after using FAST I/O. Can anyone help??

what is the need of segment trees in this question? Can you elaborate? I think this problem can be solved through pure logic. What you need to do is store the states of all the bits of all the elements in the array seperately and handle only the the ‘k’ positions adjacent to the bits which are 0…

well the logic for using segment tree was that after K rounds the ith number in the array will be influenced by (i-K)th till (i+K)th number,i.e., basically a continuous range of numbers. Hence the usage of segment tree.
Well the time complexity of my solution is and O(n) for building/test case and O(nlog(n)) for querying/test case,and in terms of number of iterations the maximum number is 3800000 per test case
and 19
10^7 for 50 test cases…which i think should pass in 3 seconds…considering 10^8 operations are performed per second.

hey

i also tried this problem just now, implemented with segment tree , and yeah same result it is. TLE
then i read this after many trails…
some forum on topcoder

I was searching for the reason but alas, i still dont know why tle came, may be cause of pyramid cluster but segment tree should pass… O(logn) per query is equivalent to no. of bits in max(all array elements). dont know why TLE 