Блог пользователя always_4ever_5_25__21_SS

Cannot figure out the reason of TLE...
Автор always_4ever_5_25__21_SS, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить