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

Can someone tell me Time complexity and Space Complexity of this Code? I am confused about it.
Автор .dragonman164, история, 15 месяцев назад, По-английски

I want to find out time complexity and space complexity of this code.

https://cses.fi/paste/4c432ea7de710eac40593c/

I was trying to solve this task but I was getting TLE.

https://cses.fi/problemset/task/1734

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by .dragonman164 (previous revision, new revision, compare).

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Wow, you really have no clue. I guess you just think that segment tree is magic.

Time complexity is $$$O(n \log^2 n + qn \log n)$$$, space complexity is $$$O(n \log n + qn)$$$ ($$$qn$$$ part might not be true, I'm not sure how is it measured).

→ Ответить