abc130_d
数列が与えられて、その数列の連続部分列で、総和がK以上のものを数え上げる
数列は最大10^5まで
まずは素朴なもの(といっても累積和は使ってしまったのでもっと素朴な書き方ができるが…) code:python
def solve(N, K, XS):
from itertools import accumulate
acc = 0 + list(accumulate(XS)) ret = 0
for i in range(N):
for j in range(i + 1, N + 1):
ret += 1
return ret
で、これだと二乗のオーダーで10^10なので、片方をlog Nに変える
code:python
def solve(N, K, XS):
import bisect
from itertools import accumulate
acc = 0 + list(accumulate(XS)) ret = 0
for i in range(N):
j = bisect.bisect_left(acc, lb)
ret += N + 1 - j
return ret