chor123's blog

By chor123, history, 12 days ago, In English

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

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +22 Vote: I do not like it

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).