Sohsoh84's blog

By Sohsoh84, history, 4 months ago, In English

Hi :), I was solving 1278D - Segment Tree, I looped over all 2n cells once and I did an O(1) process inside the loop, then I looped again over them and in each index, I called either "Update" or "Sum" method of a Fenwick tree with size MAXN(about 1e6 in this problem), I think the final time complexity is going to be O(N log N) and my code should pass test cases with this time complexity, but I've got TLE on test 15

am I doing something wrong so it caused an undefined behavior ?? or Fenwick tree isn't good for this problem ??

My code: 83112181

and sorry for my bad English :)

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

seg.erase(seg.begin()); You do this like n times on a vector.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I'm so stupid, you are right, I did the same thing with an array and I passed the testcase 15, thank you very much :)