Problem:


Score : 600 points

Problem Statement

We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq  i < N ) holds.

Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.

Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?

Constraints

-10^8 \leq X, D \leq 10^8

1 \leq N \leq 2 \times 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X D

Output

Print the number of possible values of S - T.

Sample Input 1

3 4 2

Sample Output 1

8

A is (4, 6, 8).

There are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), and ((4, 6, 8), ()).

The values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18, respectively, so there are eight possible values of S - T.

Sample Input 2

2 3 -3

Sample Output 2

2

A is (3, 0). There are two possible values of S - T: -3 and 3.

Sample Input 3

100 14 20

Sample Output 3

49805



Sample input:
3 4 2


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
# Sum Difference
N, X, D = map(int, input().split())
if D < 0:
    X, D = -X, -D
# D>=0 として一般性を失わない
if D == 0:
    Sets = set()
    for i in range(N+1):
        Sets.add(i*X)
    print(len(Sets))
    exit()

# D>0
ans = 0
Sets = set()

#TLE O(N**3)
for j in range(N+1):
    for k in range((j-1)*j//2, (2*N-1-j)*j//2+1):
        Sets.add(X*j+D*k)
print(len(Sets))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,x,d=map(int,input().split())
    s=set()
    s_add=s.add
    for k in range(n+1):
        for j in range(k*(k-1)//2, 1+k*(2*n-k-1)//2):
            s_add(j*d+x*k)
    print(len(s))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,x,d=map(int,input().split())
    s=set()
    for k in range(n+1):
        for j in range(k*(k-1)//2, 1+k*(2*n-k-1)//2):
            s.add(j*d+x*k)
    print(len(s))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,x,d=map(int,input().split())
    s=set()
    for k in range(n+1):
        for j in range(k*(k-1)//2, 1+k*(2*n-k-1)//2):
            s.add(j*d+x*k)
    print(len(s))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
n, x, d = map(int, input().split())
if d < 0:
    d = -d
    x = -x

if d == 0:
    if x == 0:
        print(1)
    else:
        print(n+1)
    exit()

mods = [[] for _ in range(d)]


for k in range(n+1):
    l_k = k*(k-1) // 2
    r_k = l_k + k*(n-k)
    c_k = k*x + l_k*d
    size = r_k - l_k
    mods[int(c_k % d)].append((c_k, size))

ans = 0
for i, mod in enumerate(mods):
    ev = []
    for c, r in mod:
        c = (c-i) // d
        ev.append((c, 1))
        ev.append((c+r+1, -1))

    ev.sort()
    count = 0
    prev = -10**64
    for e in ev:
        size = e[0] - prev
        if count > 0:
            ans += size
        prev = e[0]
        count += e[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

x = list(map(int, input().split()))
a = [x[1]+x[2]*i for i in range(x[0])]

results = []
total = sum(a)
for i in range(x[0]+1):
  s = map(sum, itertools.combinations(a, i))
  ss = np.array(list(s))
  results.append(2*ss - total)

results = np.concatenate(results)
print(np.unique(results).shape[0])

Submission status: Time Limit Exceeded

Solution code:
import itertools

x = list(map(int, input().split()))
a = [x[1]+x[2]*i for i in range(x[0])]

results = []
total = sum(a)
for i in range(x[0]+1):
  s = map(sum, itertools.combinations(a, i))
  results += [2*ss - total for ss in s]

print(len(list(set(results))))

Submission status: Time Limit Exceeded

Solution code:
def calc_list(X):
    X.sort()
    ans = 0
    i = 0
    tmp_list = 0
    while i < len(X):
        if tmp_list == 0:
            tmp_L = X[i][0]
            tmp_list += 1
        else:
            if X[i][1] == 0:
                tmp_list += 1
            else:
                tmp_list -= 1
                if tmp_list == 0:
                    tmp_R = X[i][0]
                    ans += tmp_R - tmp_L + 1
        i += 1
    return ans
N,X,D = list(map(int,input().split()))
if D == 0:
    if X == 0:
        ans = 1
    else:
        ans = N + 1
else:
    if D < 0:
        X = -X
        D = -D
    data = [[] for i in range(D)]
    data[0].append([0,0])
    data[0].append([0,1])
    ub = 0
    lb = 0
    for i in range(N):
        lb += i
        ub += N - 1 - i
        data[((i+1)*X)%D].append([(((i+1)*X)//D)+lb,0])
        data[((i+1)*X)%D].append([(((i+1)*X)//D)+ub,1])
    ans = 0
    for i in range(D):
        if len(data[i]) != 0:
            ans += calc_list(data[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

N, X, D = map(int, read().split())

if D == 0:
    if X == 0:
        print(1)
    else:
        print(N+1)
    exit()

g = gcd(X, D)
X //= g; D //= g
if D < 0:
    X, D = -X, -D

def F(d):
    event = []
    for n in range(d, N+1, D):
        
        low = X * n // D + n * (n-1) // 2 # 右の項は総和の式から
        high = X * n // D + n * (N+N-n-1) // 2
        event.append((low, 0))
        event.append((high, 1))
    event.sort()
    overlap = 0
    cnt = 0
    for x, t in event:
        if not t:
            if not overlap:
                left_end = x
            overlap += 1
        else:
            overlap -= 1
            if not overlap:
                cnt += x - left_end + 1
    return cnt
#min(D,N+1)
answer = sum(F(d) for d in range(D))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, X, D = map(int, input().split())

AN = X + D * (N - 1)

ans_set = set()
for k in range(N + 1):
    start = k * (2 * X + (k - 1) * D) // 2
    end = k * (2 * AN - (k - 1) * D) // 2
    if D:
        for r in range(start, end + D, D):
            ans_set.add(r)
    else:
        ans_set.add(start)

print(len(ans_set))

Submission status: Time Limit Exceeded

Solution code:
N,X,D=map(int,input().split())
f,c,r={},[0]*8**9,0
for x,y,z in sorted((((N-k)*j+~-k)*k//2+k*X//D,j,k*X%D) if D else(0,j,k*(X!=0))for k in range(N+1)for j in[0,2]):
 if c[z]+y<1:
  f[z]=x
 r+=(x-f[z]+1)*(c[z]<y)
 c[z]-=y-1
print(r)

Submission status: Time Limit Exceeded

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
    quit()
  else:
    print(n + 1)
    quit()
if d < 0:
  x, d = -x, -d
lst = []
dic = {0: [0]}
for k in range(1, n + 1):
    left = (k - 1) * k // 2
    right = (2 * n - k - 1) * k // 2
    tmplst = [k * x + i * d for i in range(left, right + 1)]
    mod = k * x % d
    if mod in dic:
      dic[mod].extend(tmplst)
    else:
      dic[mod] = tmplst
c = 0
for i in dic.values():
  c += len(set(i))
print(c)

Submission status: Time Limit Exceeded

Solution code:
N,X,E=map(int,input().split())
D=E+(E==0)*10**8
f,c,r={},[0]*10**8,0
for x,y,z in sorted(((((N-k)*j+~-k)*k//2+k*X//D)*(E!=0),j,k*X%D)for k in range(N+1)for j in[0,2]):
 if c[z]+y<1:
  f[z]=x
 r+=(x-f[z]+1)*(c[z]<y)
 c[z]-=y-1
print(r)

Submission status: Time Limit Exceeded

Solution code:
N,X,D= map(int,input().split())

ans = set()
for i in range(0,N+1):
    m = (X-D)*(2*i-N)
    l = i*(i+1)//2
    r = i*N - i*(i-1)//2
    s = set([m-D*(N*(N+1)//2 -2*j) for j in range(l,r+1)])
    ans |= s
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n, x, d = [int(x) for x in input().split(" ")]
a = [x + i * d for i in range(n)]
p = set([0])

for i in range(n):
  p = p | set([c + a[i]for c in p])

print(len(p))

Submission status: Time Limit Exceeded

Solution code:
n, x, d = [int(x) for x in input().split(" ")]
a = [x + i * d for i in range(n)]
p = set([0])

for i in range(n):
  p = set([c - a[i]for c in p]) | set([c + a[i]for c in p])

print(len(p))

Submission status: Memory Limit Exceeded

Solution code:
N,X,D=map(int,input().split())
f,c,r={},[0]*9**9,0
for x,y,z in sorted((((N-k)*j+~-k)*k//2+k*X//D,j,k*X%D) if D else(0,j,k*(X!=0))for k in range(N+1)for j in[0,2]):
 if c[z]+y<1:
  f[z]=x
 r+=(x-f[z]+1)*(c[z]<y)
 c[z]-=y-1
print(r)

Submission status: Memory Limit Exceeded

Solution code:
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r=[0]*abs(D),[0]*abs(D),0
 for x,y,z in sorted(((N-k)*k*j+~-k*k//2+k*X//D,j,k*X%D)for k in range(N+1) for j in[0,1]):
  r+=(x-f[z]+1)*(c[z]<2)*y
  if c[z]+y<1:
   f[z]=x
  c[z]-=2*y-1
print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
Sの通り数で良い

X+D ~ X+(N-1)*D まで
a個とったとして，aX + bDの形になる.add()
Dの個数bについて，minとmaxを考えれば，その間は全部作れるはず

N,X,D=5,4,2
[4,6,8,10,12]からa=3個選ぶ場合
3X+3D ~ 3X+9Dまでの7通り作れる，

a個選ぶ場合，Dの係数は
min b : (a-1)*a // 2            ... 0~(a-1)までの和
max b  : a*(N-1) - (a-1)*a // 2      ... (N-a)~(N-1)までの和

通り数： a*(N-1) - 2*((a-1)*a // 2) + 1

ここからXとDが変動した時のかぶりをどうするか

aを決め打つと，表せる範囲は等差数列になる（等差D）
結局，いろんな等差数列が出てくるのでそれらで表せるものを探す．

min b = L
max b = Rとする
RーL = R'とする
初項Ca = a*X + D*Lとする

この数列はCa ~ Ca + D*R'

(a*X)mod D の値が異なれば絶対に同じ値にはならない
mod Dごとにグループを分けて考える，
各グループでCa/D =Ca'として
Ca' ~ Ca'+R'　の区間を考える．どこかの区間に入っていればOK
=>イベントソート，+1と−１

"""
def main():
    N,X,D=MI()
    if D==0:
        if X==0:
            print(1)
            exit()
        else:
            print(N+1)
            exit()
            
    #グルーピング
    from collections import defaultdict
    dd = defaultdict(list)
    for a in range(N+1):
        L = ((a-1)*a)//2
        R = a*(N-1) - ((a-1)*a)//2
        R2 = R-L
        Ca = a*X + D*L
        key=(a*X)%D
        dd[key].append([Ca//D , Ca//D + R2])
        
    #イベントそーと
    ans=0
    for k,vs in dd.items():
        E=[]
        for v in vs:
            E.append([v[0],1])
            E.append([v[1]+1,-1])
        E.sort()
        
        # print(k,vs)
        # print(E)
        
        now=-10**10
        score=0
        for e in E:
            nxt=e[0]
            diff=nxt-now
            if score>=1:
                ans+=diff
            score+=e[1]
            now=nxt
            
    print(ans)
            
            
        
    


    

main()

Submission status: Accepted

Solution code:
n, x, d = map(int, input().split())

if d == 0:
  if x == 0:
    print(1)
    exit()
  else:
    print(n + 1)
    exit()
if d < 0:
  y = x
  x = x + d * (n - 1)
  d = -d
else:
  y = x + d * (n - 1)
  
U = {}
ans = 0
has0 = 0
for k in range(1, n + 1):
  r = (x * k) % d
  s = k * d * (k - 1) // 2
  v1 = k * x + s
  v2 = k * y - s
  if r in U:
    u = U[r]
    if v1 > u[1] or v2 < u[0]:
      ans += (u[1] - u[0]) // d + 1
    else:
      v1 = min(v1, U[r][0])
      v2 = max(v2, U[r][1])
  U[r] = (v1, v2)
  if r == 0 and v1 <= 0 and v2 >= 0:
    has0 = 1
#  print(ans, k, v1, v2, U)

for r, u in U.items():
  ans += (u[1] - u[0]) // d + 1

if not has0: ans += 1
  
print(ans)

Submission status: Accepted

Solution code:
LI = lambda: list(map(int, input().split()))

N, X, D = LI()


def sumeq(n):
    return n * (n + 1) // 2


def main():
    if D == 0:
        if X == 0:
            ans = 1
        else:
            ans = N + 1
        print(ans)
        return
    
    d = {}
    for i in range(N + 1):
        a = i * X + sumeq(i - 1) * D
        b = sumeq(N - 1) - sumeq(N - i - 1) - sumeq(i - 1)
        v = (a - a % D) // D
        if a % D in d:
            d[a % D].append((v, b))
        else:
            d[a % D] = [(v, b)]
    
    ans = 0
    for w in d.values():
        w.sort()
        ans += w[0][1] + 1
        x = w[0][0] + w[0][1]
        n = len(w)
        for i in range(1, n):
            r = w[i][0] + w[i][1]
            if x < w[i][0]:
                ans += w[i][1] + 1
            elif x < r:
                ans += r - x
            x = max(x, r)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys
#import numpy as np

def solve(N, X, D):
    if D == 0:
        if X == 0:
            return 1
        return N+1
    #L = {0: [(0, 1), (1, -1)]}
    L = [[(0, 1), (1, -1)]]
    mapping = {0: 0}
    coef_l = 0
    coef_r = 1
    for coef_x in range(1, N+1):
        m = X * coef_x % D
        l = X * coef_x // D + coef_l
        r = X * coef_x // D + coef_x * N - coef_r
        coef_l = coef_r
        coef_r += coef_x + 1
        if m not in mapping:
            mapping[m] = len(L)
            L.append([(0, 0)] * 0)
        idx_L = mapping[m]
        L[idx_L].append((l, 1))
        L[idx_L].append((r+1, -1))
    ans = 0
    for Q in L:
        Q.sort()
        cnt = 0
        last = None
        for val, sign in Q:
            if cnt > 0:
                ans += val - last
            cnt += sign
            last = val
    return ans

# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8,i8)"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


N, X, D = map(int, input().split())
print(solve(N, X, D))

Submission status: Accepted

Solution code:
def solve(N, X, D):
    if D == 0:
        if X == 0:
            return 1
        return N+1
    L = {0: [(0, 1), (1, -1)]}
    coef_l = 0
    coef_r = 1
    for coef_x in range(1, N+1):
        m = X * coef_x % D
        l = X * coef_x // D + coef_l
        r = X * coef_x // D + coef_x * N - coef_r
        coef_l = coef_r
        coef_r += coef_x + 1
        if m not in L:
            L[m] = []
        L[m].append((l, 1))
        L[m].append((r+1, -1))
    ans = 0
    #print(L)
    for Q in L.values():
        Q.sort()
        cnt = 0
        last = None
        for val, sign in Q:
            if cnt > 0:
                ans += val - last
            cnt += sign
            last = val
    return ans

N, X, D = map(int, input().split())
print(solve(N, X, D))

Submission status: Accepted

Solution code:
from collections import *

N, X, D = map(int, input().split())

if D==0:
    if X==0:
        print(1)
    else:
        print(N+1)
        
    exit()
    
l = []

for i in range(N+1):
    L = i*(i-1)//2
    U = i*(2*N-i-1)//2
    
    if D>0:
        l.append((i*X+L*D, U-L+1))
    else:
        l.append((i*X+U*D, U-L+1))

d = defaultdict(list)

for li in l:
    d[li[0]%abs(D)].append(li)

ans = 0

for v in d.values():
    m = min(vi[0] for vi in v)
    lr = []
    
    for vi in v:
        l = (vi[0]-m)//abs(D)
        r = l+vi[1]-1
        lr.append((l, r))
        
    events = []
    
    for li, ri in lr:
        events.append((li, 1))
        events.append((ri+1, -1))
    
    events.sort(key=lambda t: t[0])
    now = 0
    
    for event in events:
        now += event[1]
        
        if now==0:
            ans += event[0]-left
        elif event[1]==1 and now==1:
            left = event[0]

print(ans)

Submission status: Accepted

Solution code:
# Sum Difference
from collections import defaultdict
N, X, D = map(int, input().split())
if D < 0:
    X, D = -X, -D

if D == 0:
    Sets = set()
    for i in range(N+1):
        Sets.add(i*X)
    print(len(Sets))
    exit()

# D>0
ans = 0
Mode = defaultdict(list)
for i in range(N+1):
    L = (i*X+D*i*(i-1)//2-i*X % D)//D
    R = (i*X+D*i*(2*N-1-i)//2-i*X % D)//D
    Mode[i*X % D].append((L, 1))
    Mode[i*X % D].append((R+1, -1))
Data = []
for key in Mode.keys():
    Mode[key].sort()
    cnt = 1
    sums = Mode[key][0][0]
    for num, which in Mode[key][1:]:
        Data.append((sums, num, cnt))
        cnt += which
        sums = num
ans = 0
for l, r, v in Data:
    if v > 0:
        ans += r-l
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,d = list(map(int, input().split()))
if d==0:
    if x==0:
        ans = 1
    else:
        ans = n+1
else:
    if d<0:
        x *= -1
        d *= -1
#         x = x + d*(n-1)
#         d *= -1
    D = {} # (要素数, 最大値)
    for i in range(n+1):
        # iX+sD
        if x!=0:
            ii = i*x % d
            jj = (i*x-ii)//d
        else:
            ii = 0
            jj = 0
#         print(ii,jj)
        if ii not in D:
            D[ii] = []
        D[ii].append((i*(i-1)//2 + jj, (2*n-1-i)*i//2 + jj))
    ans = 0
    for k,v in D.items():
        v.sort()
        m = -float("inf")
        val = 0
        for l,r in v:
#             val += (r - (max(l-1, m)))
            val += max(r - (max(l-1, m)), 0)
            m = max(m, r)
        ans += val
                    
#         num = ((2*n-1-i)*i//2 + jj) - max(i*(i-1)//2 + jj - 1, m if m is not None else -float("inf"))
#         D[ii] = [D[ii][0]+num, (2*n-1-i)*i//2 + jj]
#         print(D)
#         if ii==0 and (2*n-1-i)*i//2 + jj >= 0 >= i*(i-1)//2 + jj:
#             zz = True
#     ans = sum(v[0] for k,v in D.items() if v[1] is not None) + (not zz)
# print(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

N,X,D = map(int,sys.stdin.readline().rstrip().split())

if D == 0:
    if X == 0:
        print(1)
    else:
        print(N+1)
    exit()

from collections import defaultdict

d = defaultdict(list)
for a in range(N+1):
    d[(a*X)%D].append(((a*X-(a*X)%D)//D+a*(a-1)//2,1))
    d[(a*X)%D].append(((a*X-(a*X)%D)//D+(N-1)*a-a*(a-1)//2+1,-1))

from itertools import accumulate

ans = 0
for i in d.keys():
    d[i].sort()
    l = len(d[i])
    A = [d[i][j][0] for j in range(l)]
    B = [d[i][j][1] for j in range(l)]
    C = list(accumulate(B))
    r,s = 0,0
    for j in range(l):
        if s == 0:
            r = A[j]
            s = 1
        elif C[j] == 0:
            ans += A[j]-r
            s = 0

print(ans)

Submission status: Accepted

Solution code:
N, X, D = map(int, input().split())

if not D:
  if not X:
    print(1)
  else:
    print(N+1)

else:
  num_dict = dict()
  ans = 0
  for i in range(N+1):
    left_num = int(i*X/D) + int(i*(i-1)/2)
    right_num = int(i*X/D) + int(i*(2*N-1-i)/2)
    judge_num = i*X%D
    if not judge_num in num_dict:
      num_dict[judge_num] = [(left_num,right_num)]
    else:
      num_dict[judge_num].append((left_num,right_num))

  for j,k in num_dict.items():
    new_k = sorted(k)
    L = new_k[0][0]
    R = new_k[0][1]
    for l in new_k:
      if l[0] <= R <= l[1]:
        R = l[1]
      elif R < l[0] and R < l[1]:
        ans += R-L+1
        L, R = l[0], l[1]
    ans += R-L+1
    
  print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, X, D = map(int, input().split())

if not D:
  if not X:
    print(1)
  else:
    print(N+1)

else:
  num_dict = dict()
  ans = 0
  for i in range(N+1):
    left_num = int(i*X/D) + int(i*(i-1)/2)
    right_num = int(i*X/D) + int(i*(2*N-1-i)/2)
    judge_num = i*X%D
    if not judge_num in num_dict:
      num_dict[judge_num] = [(left_num,right_num)]
    else:
      num_dict[judge_num].append((left_num,right_num))

  for j,k in num_dict.items():
    new_k = sorted(k)
    L = new_k[0][0]
    R = new_k[0][1]
    for l in new_k:
      if l[0] <= R <= l[1]:
        R = l[1]
      elif R < l[0] and R < l[1]:
        ans += R-L+1
        L, R = l[0], l[1]
    ans += R-L+1
    
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
  else:
    print(n+1)
  exit()
L = []
C = defaultdict(int)
D = defaultdict(int)
for i in range(n+1):
  q, r = divmod(x*i, d)
  a = i*(i-1)//2
  b = i*(2*n-i-1)//2
  a += q
  b += q
  L.append((a, r, 1))
  L.append((b+1, r, -1))
L.sort()
ans = 0
for p, idx, b in L:
  if C[idx] > 0:
    ans += p - D[idx]
  C[idx] += b
  D[idx] = p
print(ans)

Submission status: Accepted

Solution code:
def examE():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    dp = [0]*(H*W)
    cur = abs(A[0][0] - B[0][0])
    dp[0] |= (1 << cur)
    for i in range(H):
        for j in range(W):
            now = dp[i*W + j]
            if i < H - 1:
                cur = abs(A[i + 1][j] - B[i + 1][j])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[(i+1)*W +j] |= (ni | ex)
            if j < W - 1:
                cur = abs(A[i][j + 1] - B[i][j + 1])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[i*W +j+1] |= (ni | ex)
    #print(dp[-1])
    ans = inf
    for i,f in enumerate(str(bin(dp[-1]))[::-1]):
        if f=="1":
            ans = i
            break
    print(ans)
    return

def examF():
    N, X, D = LI()

    if D==0:
        ans = N + 1
        if X==0:
            ans = 1
        print(ans)
        return

    if D<0:
        X, D = -X, -D

    S = defaultdict(list)
    for i in range(N+1):
        base = (X*i) % D
        start = (X*i) // D + i*(i-1)//2
        end = (X*i) // D + i*(N-1 + N -i)//2
        S[base].append([start,end])
    #print(S)

    ans = 0
    for d in S.values():
        d.sort()
        L, R = d[0]
        if len(d)==1:
            ans += R - L + 1
            continue

        for l,r in d[1:]:
            if r<=R:
                continue
            if R<l:
                ans += R - L + 1
                L, R = l, r
            elif R<r:
                R = r
        ans += R - L + 1
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

Submission status: Accepted

Solution code:
def solve():
    N, X, D = map(int, input().split())

    if D == 0:
        if X == 0:
            print(1)
        else:
            print(N+1)
        return

    LRss = {}
    for k in range(N+1):
        m = X*k
        rem = m%D
        minCoef = m//D + k*(k-1)//2
        maxCoef = m//D + k*(2*N-k-1)//2
        if rem not in LRss:
            LRss[rem] = [(minCoef, maxCoef)]
        else:
            LRss[rem].append((minCoef, maxCoef))

    ans = 0
    for rem, LRs in LRss.items():
        LRs.sort()
        LNow, RNow = LRs[0]
        for L, R in LRs[1:]:
            if L <= RNow:
                if R > RNow:
                    RNow = R
            else:
                ans += RNow - LNow + 1
                LNow, RNow = L, R
        ans += RNow - LNow + 1

    print(ans)


solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, x, d = nm()
  ans = 0
  if d == 0:
    print(1 if x == 0 else n+1)
    return
  if d < 0:
    d = -d
    x = -x
  g = dict()
  g[0] = [(0, 0)]
  for i in range(1, n+1):
    c, y = divmod(x * i, d)
    # print((c, y))
    f = (c + i*(i-1)//2, c + n*i - i*(i+1)//2)
    if y not in g:
      g[y] = list()
    g[y].append(f)
  for y in g:
    f = sorted(g[y])
    # print(f)
    cx, cy = f[0]
    for nx, ny in f:
      if nx <= cy:
        cx = min(nx, cx)
        cy = max(ny, cy)
      else:
        ans += cy - cx + 1
        cx, cy = nx, ny
    ans += cy - cx + 1
  print(ans)
  return

solve()

Submission status: Accepted

Solution code:
N,X,D = map(int,input().split())
if D==0:
    print(1 if X==0 else N+1)
    exit()
if D < 0:
    D *= -1
    X -= D*(N-1)

from collections import defaultdict
arrs = defaultdict(lambda: defaultdict(lambda: 0))
mni = mxi = 0
for k in range(N+1):
    d,m = divmod(k*X + D*mni, D)
    l = mxi - mni + 1
    arrs[m][d] += 1
    arrs[m][d+l] -= 1
    mni += k
    mxi += N-k-1

ans = 0
for arr in arrs.values():
    p = None
    c = 0
    for x,v in sorted(arr.items()):
        if c > 0:
            ans += x-p
        c += v
        p = x
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, X, D = map(int, input().split())
if D == 0:
  if X == 0: print(1)
  else: print(N + 1)
  exit(0)
a = dd(list)
a[0].append((0, 0))
d = abs(D) // abs(gcd(X, D))
#print(d)

for i in range(1, N + 1):
  l = X * i + D * i * (i - 1) // 2
  r = X * i + D * (i * N - i * (i + 1) // 2)
  if r < l: l, r = r, l
  a[i % d].append((l, r))

res = 0
for x in a.keys():
  s = set()
  for l, r in a[x]:
    s.add(l)
    s.add(r)
    s.add(r + 1)
  xs = sorted(s)
  table = [0] * (len(xs) + 1)
  for l, r in a[x]:
    ll = bl(xs, l)
    rr = bl(xs, r + 1)
    table[ll] += 1
    table[rr] += -1
  for i in range(len(xs)): table[i + 1] += table[i]
  l = xs[0]
  for i in range(len(xs)):
    if table[i]:
      if l == -1: l = xs[i]
      continue
    res += (xs[i - 1] - l) // abs(D) + 1
    l = -1

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, X, D = map(int, input().split())

if D == 0:
    ans = N+1 if X != 0 else 1
else:
    C = {}
    Que = {}
    for l in range(N+1):
        start = l*X//D + l*(l-1)//2
        end = start + l*(N-l)
        key = l*X%D
        if key in Que:
            Que[key].append((start, end))
            C[key] += [start, end, start+1, end+1, start-1, end-1]
        else:
            Que[key] = [(start, end)]
            C[key] = [start, end, start+1, end+1, start-1, end-1]


    ans = 0
    for key, List in C.items():
        ind_to_co = sorted(list(set(List)))
        co_to_ind = {a:i for i, a in enumerate(ind_to_co)}

        Imos = [0]*(len(ind_to_co)+1)
        for start, end in Que[key]:
            Imos[co_to_ind[start]] += 1
            Imos[co_to_ind[end+1]] -= 1

        for i in range(len(ind_to_co)-1):
            a = ind_to_co[i]; b = ind_to_co[i+1]
            Imos[i+1] += Imos[i]
            if Imos[i+1] > 0 and Imos[i] > 0:
                ans += b-a
            elif Imos[i] > 0:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,a,d=map(int,input().split())

dic={}

ans=0

if d==0:
    if a==0:
        print(1)
    else:
        print(n+1)
else:
    for k in range(n+1):
        l=k*a+k*(k-1)*d//2
        r=l+k*(n-k)*d
        idx=l%d
        l//=d
        r//=d
        if idx in dic:
            prel,prer=dic[idx]
            #共通部分ありか、なしかで分岐
            if prer<l or prel>r:
                dic[idx]=(l,r)
                ans+=r-l+1 
            else:
                nl=min(prel,l)
                nr=max(prer,r)
                ans+=prel-nl+nr-prer
                dic[idx]=(nl,nr)
        else:
            ans+=r-l+1 
            dic[idx]=(l,r)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, x, d = map(int, input().split())

if d == 0:
    if x == 0:
        ans = 1
    else:
        ans = n + 1
else:
    if d < 0:
        x, d = -x, -d

    intervals = defaultdict(list)
    for i in range(n + 1):
        # [l, r]
        l = i * (i - 1) // 2
        r = i * (2 * n - i - 1) // 2

        a = (x * i) % d
        b = (x * i) // d
        intervals[a].append((l + b, r + b))  # [l, r]
    # print(intervals)

    ans = 0
    for interval in intervals.values():
        interval.sort()

        l, r = interval[0]
        ans += r - l + 1
        for i in range(1, len(interval)):
            li, ri = interval[i]
            if ri <= r:
                continue
            elif li <= r:
                ans += ri - (r + 1) + 1
                l, r = li, ri
            else:
                ans += ri - li + 1
                l, r = li, ri

print(ans)

Submission status: Accepted

Solution code:
n,x,d = map(int, input().split())
if d<0:
    d = -d
    x = -x

if d != 0:
    ans = 0
    it = list()
    for i in range(n+1):
        it.append((i*x%d,i))
    it.sort()
    prev = -1
    lsall = []
    ls = [100,-100]
    for idx,i in it:
        if prev != idx:
            lsall.append(ls)
            lsall.sort()
            mnp_,mxp_ = lsall[0]
            for j in range(1,len(lsall)):
                mn_,mx_ = lsall[j]
                if mxp_ < mn_:
                    mxp_ = mx_
                    mnp_ = mn_
                else:
                    ans -= mxp_-mn_+1
                    mxp_ = max(mx_,mxp_)
                    mnp_ = min(mn_,mnp_)
            lsall = list()
            ls = None
            prev = idx
        plus = x*i//d
        mn = i*(i-1)//2 + plus
        mx = i*(n-1+n-i)//2 + plus
        if ls is None:
            ans += mx - mn + 1
            ls = [mn,mx]
        else:
            mnp,mxp = ls
            if mxp + 1 < mn or mnp - 1 > mx:
                ans += mx - mn + 1
                lsall.append(ls)
                ls =[mn,mx]
            else:
                ans += max(mx-mxp,0)
                ans += max(mnp-mn,0)
                ls = [min(mn,mnp),max(mx,mxp)]
    
    

    lsall.append(ls)
    lsall.sort()
    mnp,mxp = lsall[0]
    for i in range(1,len(lsall)):
        mn,mx = lsall[i]
        if mxp < mn:
            mxp = mx
            mnp = mn
        else:
            ans -= mxp-mn+1
            mxp = max(mx,mxp)
            mnp = min(mn,mnp)
    print(ans)
else:
    if x != 0:
        print(n+1)
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict

INF = float("inf")

N, X, D = map(int, input().split())

if D == 0:
    print(1 if X == 0 else N + 1)
    quit()

if D < 0:
    X, D = -X, -D

memo = defaultdict(list)
for k in range(N + 1):
    l = k * X + (k - 1) * k // 2 * D
    r = k * X + (N - k + N - 1) * k // 2 * D
    memo[l % D].append((l, r))

ans = 0
for LR in memo.values():
    LR.sort()

    cur = -INF
    for l, r in LR:
        if cur < l:
            ans += (r - l) // D + 1
            cur = r
        if cur < r:
            ans += (r - cur) // D
            cur = r

print(ans)