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: Wrong Answer

Solution code:
from collections import *

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

if D==0:
    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: Wrong Answer

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 = {} # (要素数, 最大値)
    zz = False
    vals = []
    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))
            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: Wrong Answer

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:
    x = x + d*(n-1)
    d *= -1    
if d==0:
    ans = n
else:
    D = {} # (要素数, 最大値)
    zz = False
    for i in range(1,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] = [0,None]
        nn, m = D[ii]
        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)

Submission status: Wrong Answer

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:
    x = x + d*(n-1)
    d *= -1
    
if d==0:
    ans = n
else:
    D = {} # (要素数, 最大値)
    zz = False
    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] = [0,None]
        nn, m = D[ii]
        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)

Submission status: Wrong Answer

Solution code:
import sys

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

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

if D < 0:
    X *= -1
    D *= -1

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: Wrong Answer

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 = i*X//D + i*(i-1)//2
    right_num = i*X//D + 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():
    ans_set = set()
    if D < 0:
      for l in k:
        range_set = {i for i in range(l[1],l[0]+1)}
        ans_set |= range_set
    else:
      for m in k:
        range_set = {i for i in range(m[0],m[1]+1)}
        ans_set |= range_set
    ans += len(ans_set)
  print(ans)

Submission status: Wrong Answer

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():
    ans_set = set()
    if D < 0:
      for l in k:
        range_set = {i for i in range(l[1],l[0]+1)}
        ans_set |= range_set
    else:
      for m in k:
        range_set = {i for i in range(m[0],m[1]+1)}
        ans_set |= range_set
    ans += len(ans_set)
  print(ans)

Submission status: Wrong Answer

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
        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: Wrong Answer

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

    if D == 0:
        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: Wrong Answer

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(0 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: Wrong Answer

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(0 if x == 0 else n)
    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: Wrong Answer

Solution code:
import sys
from fractions import gcd
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 = [(0, 0)]
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.append((l, r))
#print(a)
d = abs(D) // abs(gcd(X, D))
#print(d)
res = 0
for i in range(N + 1):
  l, r = a[i]
  t = 1 + (r - l) // abs(D)
  if i + d <= N:
    if r >= a[i + d][0]: t -= 1 + (r - a[i + d][0]) // abs(D)
  if t > 0: res += t
  #print(t)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
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 = [(0, 0)]
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.append((l, r))
a.sort()
#print(a)
d = abs(D) // abs(gcd(X, D))
#print(d)
res = 0
for i in range(N + 1):
  l, r = a[i]
  t = 1 + (r - l) // abs(D)
  if i + d <= N:
    if r >= a[i + d][0]: t -= 1 + (r - a[i + d][0]) // abs(D)
  if t > 0: res += t
  #print(t)
print(res)

Submission status: Wrong Answer

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

dic={}

ans=0

if d==0:
    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: Wrong Answer

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(0)

Submission status: Wrong Answer

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:
    print(n+1)

Submission status: Wrong Answer

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
    for idx,i in it:
        if prev != idx:
            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
            flag = False
            if mxp + 1 < mn or mnp - 1 > mx:
                ans += mx - mn + 1
                ls =[mn,mx]
            else:
                ans += max(mx-mxp,0)
                ans += max(mnp-mn,0)
                ls = [min(mn,mnp),max(mx,mxp)]

    print(ans)
else:
    print(n+1)

Submission status: Wrong Answer

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

if d != 0:
    ans =1
    if x%d == 0 and 0 <= -x//d < n:
        ans -= 1

    it = list()
    for i in range(1,n+1):
        it.append((i*x%d,i))
    if x>=0:
        it.sort()
    else:
        it.sort(reverse=True)
    prev = -1
    for idx,i in it:
        if prev != idx:
            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:
                ans += mx-mn+1
                ls = [mn,mx]
            else:
                ans += mx-mxp
                ls = [mnp,mx]

    print(ans)
else:
    print(n+1)

Submission status: Wrong Answer

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

if d != 0:
    ans =1
    ls = [None]*d

    for i in range(1,n+1):
        plus = x*i//d
        mn = i*(i-1)//2 + plus
        mx = i*(n-1+n-i)//2 + plus
        idx = x*i%d
        if ls[idx] is None:
            ans += mx - mn + 1
            ls[idx] =[mn,mx]
        else:
            mnp,mxp = ls[idx]
            if mxp + 1 < mn:
                ans += mx-mn+1
                ls[idx] = [mn,mx]
            else:
                ans += mx-mxp
                ls[idx] = [mnp,mx]

    print(ans)
else:
    print(n+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# F

import sys
from heapq import heappop, heappush

N, X, D = map(int, input().split())
if D < 0:
    X, D = -X, -D

l_mod = [[] for _ in range(D)]

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

for x in range(N+1):
    l_mod[(x*X) % D].append(x)

# print(l_mod)

ans = 0
for s, ks in enumerate(l_mod):
    d = []
    for k in ks:
        l = (k-1)*k//2
        r = (N-k+(N-1))*k //2
        # print(k, l, r)

        l = (k * X - s) // D + l
        r = (k * X - s) // D + r
        heappush(d, (l, 1, l == r))
        heappush(d, (r, -1, l == r))
    # print(d)

    prev_val = 0
    prev_idx = - float('inf')
    res = {}
    while len(d) > 0:
        idx, tp, flg = heappop(d)
        val = prev_val + tp
        res[idx] = val
        prev_val = val
        prev_idx = idx
    # print(res)
    v_prev = 0
    i_prev = None

    for k, v in res.items():
        if v_prev > 0:
            ans += k - i_prev + 1
        if v_prev == 0 and v == 0:
            ans += 1
        v_prev, i_prev = v, k

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

INF = float("inf")

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

if D == 0:
    print(0 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)

Submission status: Wrong Answer

Solution code:
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)

print(len(s))

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if x == 0 and d == 0:
	print(1)
	sys.exit()
elif d == 0:
	print(n+1)
	sys.exit()

if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d

if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d

if x < 0:
	x, d = x + (n-1) * d, -d

g = gcd(x, d)

ans = 1
for i in range(1, n+1):
	k = max((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (i-1) // 2 - 1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d

if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d

if x < 0:
	x, d = x + (n-1) * d, -d

g = gcd(x, d)

ans = 1
for i in range(1, n+1):
	k = max((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (i-1) // 2 - 1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())
"""
数列からi個選ぶことを考えると
i*xに加えて足されるdの数はi(i-1)/2 〜 i(2n-1-i)/2 の任意の個数
i > j なるjで代替されるような和はこのうちどのような条件を満たすものか？
g = gcd(x, d). l = lcm(x, d)として
(g*l = x*d)
i*x + k*d が条件を満たすとすると
i*x + k*d = (i - d/g)x + (k + x/g)d が成り立つ
(i - d/g)(2n - 1 - i + d/g)/2 >= (k + x/g) となるような最大のkを求めれば，
k以下はすべてかぶる，k+1以上はすべてかぶらない
"""
if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = x + (n-1) * d, -d


g = gcd(x, d)

ans = 1
for i in range(1, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, i * (i-1) // 2 - 1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d


g = gcd(x, d)

ans = 1
for i in range(1, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, i * (i-1) // 2 - 1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d


g = gcd(x, d)

if x >= 0:
	ans = 1
	for i in range(1, n+1):
		k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, i * (i-1) // 2 - 1)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)

else:
	ans = 1
	for i in range(n-1, -1, -1):
		k = max(((i + d//g) * (2*n - 1 - i - d//g)) // 2 + x//g, i * (i-1) // 2 - 1)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())
"""
数列からi個選ぶことを考えると
i*xに加えて足されるdの数はi(i-1)/2 〜 i(2n-1-i)/2 の任意の個数
i > j なるjで代替されるような和はこのうちどのような条件を満たすものか？
g = gcd(x, d). l = lcm(x, d)として
(g*l = x*d)
i*x + k*d が条件を満たすとすると
i*x + k*d = (i - d/g)x + (k + x/g)d が成り立つ
(i - d/g)(2n - 1 - i + d/g)/2 >= (k + x/g) となるような最大のkを求めれば，
k以下はすべてかぶる，k+1以上はすべてかぶらない
"""
if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d


g = gcd(x, d)

if x >= 0:
	ans = n+1
	for i in range(2, n+1):
		k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, i * (i-1) // 2 - 1)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)

else:
	ans = 1
	for i in range(n-1, -1, -1):
		k = max(((i + d//g) * (2*n - 1 - i - d//g)) // 2 + x//g, i * (i-1) // 2 - 1)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d

ans = n+1
g = gcd(x, d)

for i in range(2, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, i * (i-1) // 2 - 1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d

ans = n
g = gcd(x, d)

for i in range(2, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, -1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, x, d = map(int, input().split())

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

    if d < 0:
        x = x + d * (N-1)
        d *= -1
    dic = defaultdict(list)

    for i in range(N+1):
        mod = (x * i) % d
        st = (i * (i+1)) // 2
        ed = (i * (N + N-i+1)) // 2
        st = st * d + (x-d) * i
        ed = ed * d + (x-d) * i
        dic[mod].append((st, ed))
    ans = 0
    for mod in dic:
        L = dic[mod]
        L.sort(key=lambda t: t[0])
        ed_prev = L[0][0] - 1
        for st, ed in L:
            if st > ed_prev:
                ans += (ed - st) // d + 1
                ed_prev = ed
            elif ed > ed_prev:
                ans += (ed - ed_prev) // d
                ed_prev = ed
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import sys
n, x, d = map(int, input().split())
if d < 0:
    d = -d
    x = -x
if d == 0:
    print(n+1 if x != 0 else 0)
    sys.exit()
g = gcd(d, x)
mod = abs(d//g)
hani = [[] for _ in range(n+1)]
for k in range(n+1):
    l = x*k+k*(k-1)//2*d
    r = x*k+k*(n*2-k-1)//2*d+d
    hani[k%mod].append((l, 0))
    hani[k%mod].append((r, 1))
ans = 0
for i in range(n+1):
    if not hani[i]:
        break
    hani[i].sort()
    cnt = 0
    l = None
    for a, f in hani[i]:
        if f == 0:#l
            if cnt == 0:
                l = a
            cnt+=1
        else:
            cnt-=1
            if cnt == 0:
                ans+=(a-l)//d
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
N, X, D = map(int, input().split())
if D == 0:
    print(N+1 if X else 1)
    exit()
g = gcd(X, D)
X //= g
D //= g
if D < 0:
    X, D = -X, -D

E = {}
for i in range(N+1):
    k = i % D
    l, r = i * (2*X+(i-1)*D) // 2, i * (2*X+(2*N-i-1)*D) // 2
    c = (r - l) // D + 1 if D else 1
    if k not in E:
        E[k] = (l, r, c)
    else:
        ll, rr, cc = E[k]
        if r < ll:
            print(1)
            E[k] = (l, rr, cc + c)
        elif l > rr:
            E[k] = (ll, r, cc + c)
        elif l < ll:
            E[k] = (l, rr, cc + ((ll - l) // D if D else 1))
        elif r > rr:
            E[k] = (ll, r, cc + ((r - rr) // D if D else 1))

ans = 0
for e in E:
    l, r, c = E[e]
    ans += c

print(ans)

Submission status: Wrong Answer

Solution code:
n, x, d = map(int, input().split())
if d == 0:
  if x == 0:
    print(1)
  else:
    print(n+1)
else:
  if d < 0:
    x, d = -x, -d
  C = [[] for _ in range(d)]
  for i in range(n+1):
    l = i*x + i*(i-1)//2
    r = (n-i)*i
    q, p = divmod(l, d)
    C[p].append((q, 0))
    C[p].append((q+r, 1))
  ans = 0
  for i in range(d):
    if not C[i]:
      continue
    C[i].sort()
    now = 0
    ft = C[i][0]
    for t, b in C[i]:
      if now > 0:
        ans += t-ft+1
      if b == 0:
        now += 1
      else:
        now -= 1
      ft = t
  print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter


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

a = [0] * n
for i in range(n - 1):
    a[i + 1] = a[i] + 1

ruiseki1 = [0] * (n + 1)
ruiseki2 = [0] * (n + 1)

for i in range(n):
    ruiseki1[i + 1] += ruiseki1[i] + a[i] 
for i in range(n):
    ruiseki2[i + 1] += ruiseki2[i] + a[n - i - 1] 

if d == 0 and x == 0:
    print(0)
    exit()
elif d == 0:
    print(n + 1)
    exit()
    
memo = {}

for i in range(n + 1):
    s_cnt = i
    geta = i * x
    div = geta // d
    mod = geta % d
    min_ = ruiseki1[i]
    max_ = ruiseki2[i]
    if mod not in memo:
        memo[mod] = []
    memo[mod].append((min_ + div, max_ + div + 1))

ans = 0
for i in memo:
    memo[i] = sorted(memo[i])
    r_max = -10**18
    for j in memo[i]:
        l, r = j
        if r - r_max < 0:
            continue
        ans += min(r - l, r - r_max)
        r_max = r
print(ans)