×

# SPOJ ANDROUND TLE

 0 http://www.spoj.com/problems/ANDROUND/ https://ideone.com/mq6vOl getting TLE even after using FAST I/O. Can anyone help?? asked 19 Dec '14, 19:41 1★abeyaar 334●2●21●40 accept rate: 30%

 0 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... answered 19 Dec '14, 19:59 947●2●10 accept rate: 25% 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. (19 Dec '14, 21:17) abeyaar1★
 0 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 :/ answered 19 Dec '14, 23:48 593●1●6 accept rate: 48% that's what i suggested!! no need for segment trees, u just need to store the state of bits in separate arrays... (20 Dec '14, 01:53) 1 but segment tree should pass.. O(logn) per query is equivalent to no. of bits in max(all array elements). dont know why TLE :/ (20 Dec '14, 11:51)
 0 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. https://github.com/imegor/spoj/blob/master/ANDROUND.cpp answered 02 Oct '18, 22:55 2★egor6174 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,768
×1,138
×184

question asked: 19 Dec '14, 19:41

question was seen: 4,919 times

last updated: 02 Oct '18, 22:57