Unexpected TLE?

Revision en6, by farmersrice, 2016-10-21 20:15:19

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 * log1012 + mlogn). 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.

Tags tle, binary search, please, help me

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)