ABC179

D was difficult, so I solved E first, then went back and solved it and got 5 questions correct.

https://gyazo.com/1b1cfda315bbb1cd751451ec5b3ff6de

https://gyazo.com/26cf926e3eaf69b4d5887fc799ae4ed5

The problem of counting the number of solutions that exist on a skipped basis.

Tends to be buggy with rounding up and down.

(3, 1, 7), (3, 2, 4), (3, 3, 1) when A=3, N=10

(3, 1, 6), (3, 2, 3) for A=3, N=9

code:python

def solve(N):

ret = N - 1

for i in range(2, N + 1):

ret += (N - 1) // i

return ret

https://gyazo.com/e62eff03c360b9b33d1aa6475b91817a

The reason I'm so tied to variables is because I debugged with print.

Bug: loop_start was off by 1 and loop_tail was taken from the end.

Finding the start of the loop is O(1)

code:python

def solve(N, X, M):

a = X

ret = []

for i in range(N):

s = sum(ret)

loop_end = i

loop_length = loop_end - loop_start

loop_count = (N - i) // loop_length

loop_left = (N - i) % loop_length

return s + loop_count * loop_sum + loop_tail

ret.append(a)

a = (a * a) % M

return sum(ret)

https://gyazo.com/c75f91099aca8b95b10f33faaa847edb

But I had not yet organized my own code only for the relative segment tree...

I was in a hurry because I had 10 minutes left.

There is also the possibility of bisecting the point at which the value changes.

But Python's bisect requires a sorted array.

That's not good, because this problem condition would cause an insertion into the array, which would be O(N).

Essentially, I should be prepared to immediately retrieve and use an equilibrium binary tree that can be used in Python...

For this problem only, "no addition to other than the beginning is necessary", so if you have it in reverse order, you get O(1) with the tail addition, but it's tricky.

Version to hold in reverse order and search for two minutes

code:python

def main():

from bisect import bisect_left

N, Q = map(int, input().split())

ret = (N - 2) ** 2

for _q in range(Q):

q, x = map(int, input().split())

if q == 1:

i = bisect_left(xs, -x)

yvals.append(x - 2)

else:

y = x

i = bisect_left(ys, -y)

xvals.append(y - 2)

print(ret)

Related Articles

---