Can be used on Marc's version as well. Benchmarks with various solutions on three worst case inputs, where the above is actually the fastest despite the O(n+m) complexity (for the 64-bit version, which seems to be the default for Windows now):
CPython 3.9.0 64-bit on Windows 10 Pro 2004 64-bit:
original 792 798 ms 795 787 ms 840 795 ms
with_abk 789 785 ms 783 790 ms 808 807 ms
with_accumulate 574 581 ms 579 581 ms 576 596 ms
Marc 732 736 ms 728 737 ms 726 736 ms
optimized_1 686 698 ms 687 702 ms 687 698 ms
optimized_2 686 696 ms 685 694 ms 679 690 ms
optimized_3 682 692 ms 678 683 ms 677 684 ms
Reinderien 516 ms 512 ms 511 ms
CPython 3.9.0 32-bit on Windows 10 Pro 2004 64-bit:
original 12191200 ms 12161229 ms 11981259 ms
with_abk 11791167 ms 11911203 ms 11821174 ms
with_accumulate 951939 ms 940937 ms 942934 ms
Marc 930922 ms 930927 ms 932923 ms
optimized_1 872865 ms 873868 ms 873869 ms
optimized_2 858863 ms 856863 ms 859868 ms
optimized_3 856851 ms 858847 ms 853842 ms
Reinderien 979 ms 959 ms 983 ms
from timeit import repeat
from random import randint
from itertools import accumulate
from randomarray import randintarray
def original(n, queries):
nums = [0] * (n + 1)
for q in queries:
nums[q[0]-1] += q[2]
nums[q[1]] -= q[2]
current = 0
max = 0
for i in nums:
current += i
if current > max: max = current
return max
def with_abk(n, queries):
nums = [0] * (n + 1)
for a, b, k in queries:
nums[a - 1] += k
nums[b] -= k
current = 0
max = 0
for i in nums:
current += i
if current > max: max = current
return max
def with_accumulate(n, queries):
nums = [0] * (n + 1)
for a, b, k in queries:
nums[a - 1] += k
nums[b] -= k
return max(accumulate(nums))
def Marc(n, queries):
indices = []
for a, b, k in queries:
indices.append((a, k))
indices.append((b + 1, -k))
indices.sort()
running_sum = 0
result = 0
for _, k in indices:
running_sum += k
result = max(result, running_sum)
return result
def optimized_1(n, queries):
changes = []
for a, b, k in queries:
changes.append((a, k))
changes.append((b + 1, -k))
changes.sort()
return max(accumulate(k for _, k in changes))
def optimized_2(n, queries):
changes = []
append = changes.append
for a, b, k in queries:
append((a, k))
append((b + 1, -k))
changes.sort()
return max(accumulate(k for _, k in changes))
def optimized_3(n, queries):
changes = [(a, k) for a, _, k in queries]
changes += [(b + 1, -k) for _, b, k in queries]
changes.sort()
return max(accumulate(k for _, k in changes))
def Reinderien(n, queries):
nums = array('q', [0]) * (n + 1)
for a, b, k in queries:
nums[a - 1] += k
nums[b] -= k
return max(accumulate(nums))
funcs = original, with_abk, with_accumulate, Marc, optimized_1, optimized_2, optimized_3, Reinderien
names = [func.__name__ for func in funcs]
def worst_case():
n = 10**7
m = 2 * 10**5
queries = [sorted([randint(1, n), randint(1, n)]) + [randint(0, 10**9)]
for _ in range(m)]
return n, queries
# Check correctness
n, queries = worst_case()
expect = funcs[0](n, queries)
for func in funcs[1:]:
print(func(n, queries) == expect, func.__name__)
# Benchmark
tss = [[] for _ in funcs]
for _ in range(3):
n, queries = worst_case()
for func, ts in zip(funcs, tss):
t = min(repeat(lambda: func(n, queries), number=1))
ts.append(t)
print()
for name, ts in zip(names, tss):
print(name.rjust(max(map(len, names))),
*(' %d%4d ms' % (t * 1000) for t in ts))