TLE on test 3 even with qlogn time complexity.

Revision en1, by GhostRider2k2, 2022-05-29 06:17:32

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: https://codeforces.com/contest/1679/submission/158765682

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?

Tags data structures, time complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English GhostRider2k2 2022-05-29 06:17:32 1013 Initial revision (published)