SPOJ ANDROUND TLE

abeyaar · December 19, 2014, 7:41pm

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

gvaibhav21 · December 19, 2014, 7:59pm

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…

dracowane · December 19, 2014, 11:48pm

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

egor6174 · October 2, 2018, 10:55pm

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.

github.com

imegor/spoj/blob/master/ANDROUND.cpp


/*Created by Karan Kanojia 
https://www.spoj.com/problems/ANDROUND/ */

#include <bits/stdc++.h>
#define MAX 1111111
#define lim 1e9+7
#define ll long long 
#define SQRT 1060
#define sci(a) scanf("%d", &a)
#define scl(a) scanf("%lld", &a)
#define pfi(a) printf("%d\n", a)
#define pfl(a) printf("%lld\n", a)
#define pfcase(t) printf("Case #%d:\n",t);
#define pf(d) printf("%s\n",d);

using namespace std; 

ll arr[MAX], tree[4*MAX+1];
void init(int left, int right, int index){

This file has been truncated. show original

abeyaar · December 19, 2014, 9:17pm

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.

gvaibhav21 · December 20, 2014, 1:53am

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

dracowane · December 20, 2014, 11:51am

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

sicho_mohit · July 19, 2021, 7:45pm

Can you please elaborate your segment tree approach a little bit or give me some hints to solve this.
Thanks in advance.