GhostRider2k2's blog

By GhostRider2k2, history, 2 months ago, In English

Hello coders! I have tried the 1697C (rooks defenders problem) but I am unable to pass the 3rd test case(I am getting TLE). I am pretty sure that my code works with qlogN time complexity. Can someone please tell me where my code is failing? My submission:

In this problem, I first inserted 1 to n+1 in two sets (one for x-axis and the other for y-axis). Now I would make changes to arrays vx and vy based on the insertion and deletion of rooks (t== 1 and t==2 cases) these would take logN as I am just inserting and deleting elements from a set. Now coming to t==3 case, I would check these sets for some number lying in the range of the given coordinates (y-coordinates after x-coordinates in my code). I would correspondingly print out the correct answer. Since I am using a set (not even a multiset) and lower_bound, it should never cross logN so the worst-case time complexity would be qlogN right?

Read more »

  • Vote: I like it
  • 0
  • Vote: I do not like it