always_4ever_5_25__21_SS's blog

Cannot figure out the reason of TLE...
By always_4ever_5_25__21_SS, history, 7 years ago, In English

I am trying to solve Sereja and Brackets . I can see that n is up to 10^6. And I have seen others solutions and they are pretty much as same as mine. I cannot figure out why I am getting TLE for my submission. Cannot find anything wrong with my segment tree or if I have missed something. :(

This is my submission. 37125846

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

»
7 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Query is O(n)

if(L == R){
    return tree[node];
}

should be

if (i >= L && j <= R) return tree[node];

or else you terminate at the root (too slow)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I cant believe I missed that. I have not done seg trees for a while and I didnt use my seg tree template and missed it. Thanks. I could not even find it when i matched with my template (though that condition was there). Anyway, thanks for pointing that out and i will be more careful next time. :)

    BTW it was i <= L and R <= j.

    → Reply