Unexpected TLE?
Difference between en7 and en8, changed 4 character(s)
So, I was recently trying to solve this problem:↵
http://mirror.codeforces.com/contest/727/problem/F↵
submission at http://mirror.codeforces.com/contest/727/submission/21647053↵
↵
My algorithm should be O($n^2 * log 10^12 + m\ log\ n$). First, I determine the lowest possible prefix sum for a certain amount of removed problems. This is done with a binary search and greedy. I binary search on the condition "If we can remove a certain number of problems, can the minimum prefix sum be greater than or equal to the target?" (This is always of form TTTT...FFF). To find that condition I greedily add numbers to a running sum, and if the running sum is less than or equal to target, I remove the smallest value that occurs before or at the current index. Then, I read all m queries and binary search for the correct answer on those.↵
↵
Can anyone help me understand why I'm getting TLE? Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English farmersrice 2016-10-21 23:51:24 4 Tiny change: ' 10^12 + m\log\n$). First' -> ' 10^12 + m log n$). First'
en7 English farmersrice 2016-10-21 23:51:09 4 Tiny change: ' 10^12 + m log n$). First' -> ' 10^12 + m\log\n$). First'
en6 English farmersrice 2016-10-21 20:15:19 6 Tiny change: 'n^2 * log m + m log n' -> 'n^2 * log 10^12 + m log n'
en5 English farmersrice 2016-10-21 20:11:34 22 Tiny change: 'a certain row of numbers. This is' -> 'a certain amount of removed problems. This is'
en4 English farmersrice 2016-10-21 20:10:06 8 Tiny change: 'tting TLE?' -> 'tting TLE? Thanks.'
en3 English farmersrice 2016-10-21 20:08:50 4 Tiny change: 'd be O($n^(2) log m + m' -> 'd be O($n^2 * log m + m'
en2 English farmersrice 2016-10-21 20:08:27 2 Tiny change: 'd be O($n^2 log m + m' -> 'd be O($n^(2) log m + m'
en1 English farmersrice 2016-10-21 20:07:40 865 Initial revision (published)