When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

GhostRider2k2's blog

By GhostRider2k2, history, 22 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: 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?

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

| Write comment?
»
22 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Use Fast IO