Qualified's blog

I should not get TLE.
By Qualified, 4 years ago, In English

I am solving 181B - Сколько троек. With the constraints being $$$n <= 3000$$$ and my solution supposedly running in $$$O(n^{2})$$$. Am I missing something? 88909110.

  • Vote: I like it
  • -37
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Map with key of pair<long double, long double> would be slow, though still surprised it TLE's (actually on second thought I'm not, it is like O(n^2lgn) with rlly bad constant factor. Plug in 3000). Don't divide coordinates by 2, just multiply all coordinates by 2, and no need to work with doubles, and try not to use map in the first place (constraints are small). In general, try to avoid doubles, they are slow, and use array when you can.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since you are using map it's $$$O(n^2 \log n)$$$. Also float arithmetic consumes huge constant factor, that's probably why you are getting TLE.

→ Reply