SPOJ ANDROUND TLE

general
, ,
1

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

2

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…

3

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 1910^7 for 50 test cases…which i think should pass in 3 seconds…considering 10^8 operations are performed per second.

4

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

read this, it will help

I was searching for the reason but alas, i still dont know why tle came, may be cause of pyramid cluster :confused:

5

that’s what i suggested!! no need for segment trees, u just need to store the state of bits in separate arrays…

6

but segment tree should pass… O(logn) per query is equivalent to no. of bits in max(all array elements). dont know why TLE :confused:

1 Like
7

Try using the fact that if 2*K >= N then the answer to each index will be and of all elements in the initial array. else we use simple range query using either a BIT or segment tree. Below is my code for reference.