Problem Info
Question
I have absolutely no idea why, but my code is TLE-ing on all test cases except the first two. It seems like at least one of the slowdowns, according to my Pycharm Debugger, is reading the inputs …? Running it on test case 3 (downloaded test data) literally stops my computer from running (???)
What I’ve Tried
First, I read in all the starting and ending positions of the intervals. Only the counts are stored. Then, loop over all positions in from 0 - M twice nestedly - say these positions are x & y. A difference array for values of k adds 1 in ans[x + y] for each occurrence of x and y in the starts and subs 1 in ans[x + y + 1] for each occurrence of x and y in the ends. This is the same as doing ans[x + y] += starts[x] * starts[y] and ans[x + y + 1] -= ends[x] * ends[y]. Then you do prefix sums and output the reuslts. This seems to be O(N + M^2 + M) with minimal constant factor. M^2 is only 25 mil and N is only 500,000 yet for some reason it’s not working.
My Work
def main():
length, range_size = map(int, input().split())
# Creates and reads counters of a & b (starts & ends respectively)
starts, ends = [0 for _ in range(5001)], [0 for _ in range(5001)]
for _ in range(length):
start, end = map(int, input().split())
starts[start] += 1
ends[end] += 1
# Calculate difference array - size of 2 * M + 2 to easily avoid index out of bounds for d[M + M + 1] -= x
difference_array = [0 for _ in range(2 * range_size + 2)]
for first in range(0, range_size + 1):
for second in range(0, range_size + 1):
difference_array[first + second] += starts[first] * starts[second]
difference_array[first + second + 1] -= ends[first] * ends[second]
# Print running prefix sums
total = 0
for value in difference_array[:-1]:
total += value
print(total)
if __name__ == "__main__":
main()