Блог пользователя GhostRider2k2

Автор GhostRider2k2, история, 22 месяца назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится