Unexpected TLE?

Правка en4, от farmersrice, 2016-10-21 20:10:06

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(n2 * logm + mlogn). First, I determine the lowest possible prefix sum for a certain row of numbers. 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.

Теги tle, binary search, please, help me

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский farmersrice 2016-10-21 23:51:24 4 Tiny change: ' 10^12 + m\log\n$). First' -> ' 10^12 + m log n$). First'
en7 Английский farmersrice 2016-10-21 23:51:09 4 Tiny change: ' 10^12 + m log n$). First' -> ' 10^12 + m\log\n$). First'
en6 Английский 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 Английский 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 Английский farmersrice 2016-10-21 20:10:06 8 Tiny change: 'tting TLE?' -> 'tting TLE? Thanks.'
en3 Английский 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 Английский 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 Английский farmersrice 2016-10-21 20:07:40 865 Initial revision (published)