whatthemomooofun1729's blog

TLE on 1530D. Secret Santa
By whatthemomooofun1729, history, 17 months ago, In English

Hi, I am working on 1530D and I'm not sure why this code gets TLE on test case 4. I've calculated the time complexity several times, and it looks like O(NLogN) (there is a nested loop but it only goes through N iterations in total, and in each iteration we do an O(logN) binary search). I've also tried fast I/O, but that didn't work. Does anybody know why this code is getting TLE? Thank you!

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

»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Correct me if im wrong, but does g[i].size() have a maximum of N elements, so your code technically has a max time complexity O(N^2logN)

I think this happens when all a[i] is the same

loop is in this code

Sorry for the spoiler error, its my first time commenting

→ Reply