cschill's blog

Help: Small code, getting TLE in nlogn
By cschill, history, 2 years ago, In English

This is my short solution unfortunately I am getting a TLE. I tried to calculate and I know that it should be a TLE, since 1e6 * 3.32 * 6 * 20 > 1e8 but this is the worst case complexity and chances are it may never be reached. I have seen that other have written nlogn solution as well using binary search. Could anyone help me optimize my solution a little bit. Thank you very much https://codeforces.com/contest/1379/submission/146460768

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by cschill (previous revision, new revision, compare).

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

I tried using pragmas, but they didn't help either :(

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

i don't think you can optimize it, your complexity is (r-l)(sqrt(m)), in the test case it should do 10^9 operations per second and in other test cases it might be even more. it can be solved in o(r-l)

→ Reply