ABC179D

https://gyazo.com/7b170df6b0f48886ab9a41790797f20e

https://gyazo.com/39b5c5d2890f126f81169312eb00f3b3

After worrying for a while, skip to E.

Worries, "What, you don't want this to be too broad in scope?" ← correct

But when you look at that code, you realize, "Oh, in essence, we just need to destroy this innermost loop.

A few cleaned up codes.

code:python

def solve(N, K, SS):

for pos in range(1, N):

ret = 0

for left, right in SS:

start = pos - right - 1

end = pos - left

ret %= MOD

return ret % MOD

I saw someone on Twitter saying that it was the "Imosu Act (fifth highest of the eight hereditary titles, later demoted to sixth highest of eight)", but I don't think so. I was not aware of that.

The problem that needs to be solved is that the part of the DP calculation that calculates the sum of a range is slow because it "adds up to a lot of numbers" when the range is large.

So, we create a separate array of "sums of numbers calculated so far".

This can be made by "adding the new value to the previous value".

Whenever a sum over a wide range is needed, it can be obtained by subtracting the cumulative sum before one of the range start points from the cumulative sum at the range end point.

https://gyazo.com/7b170df6b0f48886ab9a41790797f20e

Segment trees are faster than O(N), which computes the sum by looping, because the range sum is O(logN).

The cumulative sum used in this case is O(1), which is even faster

While cumulative sums can only contain values from the beginning, segment trees can contain values at any position. This flexibility is the only reason for the slowness.

In this case, since the DP was made from the beginning, there was no need to put it in an arbitrary position.

---