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: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate


def solve(n, x, d):
    if d == 0:
        return 1 if x == 0 else n + 1
    elif d < 0:
        x, d = -x, -d

    g = gcd(x, d)
    x //= g
    d //= g

    lowers = [0] + list(accumulate(range(n)))
    uppers = [0] + list(accumulate(range(n - 1, -1, -1)))
    ans = 0
    for k_mod in range(min(n + 1, d)):
        k = k_mod
        offset = 0
        endpoints = []
        while k <= n:
            endpoints.append((lowers[k] + offset, 0))
            endpoints.append((uppers[k] + offset, 1))
            k += d
            offset += x
        endpoints.sort()
        opening = 0
        current_left = 0
        for s, t in endpoints:
            if t == 0:
                if opening == 0:
                    current_left = s
                opening += 1
            else:
                opening -= 1
                if opening == 0:
                    ans += s - current_left + 1

    return ans


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

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
f,c,r={},[0]*10**8,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: Accepted

Solution code:
from fractions import gcd
from itertools import accumulate

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

if d == 0:
    if x == 0:
        print(1)
    else:
        print(n + 1)
    exit()
elif d < 0:
    x, d = -x, -d

g = gcd(x, d)
back_k = d // g
offset = x // g

lowers = [0] + list(accumulate(range(n)))
uppers = [0] + list(accumulate(range(n - 1, -1, -1)))
min_memo = [10 ** 18] * min(n + 1, back_k)
max_memo = [-(10 ** 18)] * min(n + 1, back_k)
# print(n, x, d, g, back_k, offset)
# print(lowers)
# print(uppers)

ans = 0
for k in range(n + 1):
    min_acc = lowers[k]
    max_acc = uppers[k]

    if k < back_k:
        min_memo[k] = min_acc - offset
        max_memo[k] = max_acc - offset
        ans += max_acc - min_acc + 1
        # print(k, ans, min_acc, max_acc, max_acc - min_acc + 1)
        continue

    kk = k % back_k
    back_min = min_memo[kk]
    back_max = max_memo[kk]

    if back_max < min_acc or max_acc < back_min:
        min_memo[kk] = min_acc - offset
        max_memo[kk] = max_acc - offset
        ans += max_acc - min_acc + 1
    else:
        current = max_acc - min_acc + 1
        duplicated = min(max_acc, back_max) - max(min_acc, back_min) + 1
        ans += current - duplicated
        min_memo[kk] = min(min_acc, back_min) - offset
        max_memo[kk] = max(max_acc, back_max) - offset

    # print(k, ans, min_acc, max_acc, back_min, back_max)

print(ans)

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
f,c,r={},[0]*10**8,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: Accepted

Solution code:
N,X,D=map(int,input().split())
f,c,r={},[0]*10**8,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: Accepted

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

from collections import defaultdict

A=defaultdict(list)

A[0].append([0,0])

MIN=0
MAX=0

if D==0:
    w=1
else:
    w=D

for i in range(N):
    MIN+=X+D*i
    MAX+=X+D*(N-1-i)

    A[MIN%w].append(sorted([MIN,MAX]))

D=abs(D)
if D==0:
    if X==0:
        D=1
    else:
        D=X
ANS=0

for mod in A:
    B=A[mod]
    B.sort()
    C=[]

    for MIN,MAX in B:
        
        if C==[]:
            C.append((MIN,MAX))
        x,y=C[-1]

        if y>=MIN:
            C[-1]=(x,max(y,MAX))
        else:
            C.append((MIN,MAX))

    for MIN,MAX in C:
        ANS+=(MAX-MIN)//D+1
    
print(ANS)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 総和は一定なので高橋君が何点(?)とるかの問題に置き換えられる
# d=0かつx=0のときは1、x!=0ならn+1で確定
# d,xと-d,-xは同値なので、dを正にすることで増加数列で考える
# d,xを同じ数で割っても答えは変わらないので、互いに素にする
def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

def main():
    n, x, d = MI()
    if d == 0:
        if x == 0:
            print(1)
        else:
            print(n + 1)
        exit()
    if d < 0: d, x = -d, -x
    g = gcd(d, abs(x))
    d, x = d // g, x // g
    #print(x, d)
    # aをk個選ぶと和sはs=k*x+c*dで、cは最小で0からk-1の和
    # 最大でn-kからn-1の和
    # kを固定するとs//dは1ずつの単調増加なので、最小と最大で個数が分かる
    # sはs mod d = x*k mod dが同じなので、それで分類する
    kk = list(range(n + 1))
    kk.sort(key=lambda k: (k * x % d, k))
    #print(kk)
    ans = 0
    pmd = -1
    pl, pr = 1, 0
    for k in kk:
        l = (k * x + (k - 1) * k // 2 * d) // d
        r = (k * x + (2 * n - k - 1) * k // 2 * d) // d
        md = x * k % d
        if md == pmd and l <= pr and pl<=r:
            pl,pr=min(pl,l),max(pr,r)
        else:
            ans += pr - pl + 1
            pl, pr = l, r
        pmd = md
        #print(k, l, r, pl, pr, ans)
    ans += pr - pl + 1
    print(ans)

main()

Submission status: Accepted

Solution code:
N,X,E=map(int,input().split())
D=E+(E==0)
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+k*(E==0 and 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: Accepted

Solution code:
from fractions import gcd

def main():
    def fmin(m):
        return X * m + D * m *(m - 1)//2
    def fmax(m):
        return X * m + D * m * (2 * N - m - 1) // 2
    N, X, D = map(int, input().split())
    if D == 0:
        if X == 0:
            print(1)
        else:
            print(N + 1)
        exit(0)
    if D < 0:
        X, D = -X, -D
    if X == 0:
        print(fmax(N) // D + 1)
    else:
        ans = 0
        g = gcd(-X, D)
        loop = D // g
        for d in range(N + 1):
            dmax = fmax(d)
            dmin = fmin(d)
            if d < loop:
                ans += (dmax - dmin) // D + 1
            else:
                pmax = fmax(d - loop)
                pmin = fmin(d - loop)
                if pmax < dmax and pmin <= dmin:
                    mmin = max(dmin, pmax + D)
                    ans += (dmax - mmin) // D + 1
                elif pmax >= dmax and pmin > dmin:
                    mmax = min(dmax, pmin - D)
                    ans += (mmax - dmin) // D + 1
                elif pmax < dmax and pmin > dmin:
                    ans += (dmax - pmax) // D + (pmin - dmin) // D
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def main():
    def fmin(m):
        return X * m + D * m *(m - 1)//2
    def fmax(m):
        return X * m + D * m * (2 * N - m - 1) // 2
    N, X, D = map(int, input().split())
    if D == 0:
        if X == 0:
            print(1)
        else:
            print(N + 1)
        exit(0)
    if D < 0:
        X, D = -X, -D
    if X > 0:
        ans = 0
        g = gcd(X, D)
        loop = D // g
        for d in range(N + 1):
            if loop <= d:
                mmin = max(fmin(d), fmax(d - loop) + D)
            else:
                mmin = fmin(d)
            mmax = fmax(d)
            ans += (mmax - mmin) // D + 1
        print(ans)
    elif X == 0:
        print(fmax(N) // D + 1)
    else:
        if X + D*(N - 1) >= 0:
            ans = 0
            g = gcd(-X, D)
            loop = D // g
            for d in range(N + 1):
                dmax = fmax(d)
                dmin = fmin(d)
                if d < loop:
                    ans += (dmax - dmin) // D + 1
                else:
                    pmax = fmax(d - loop)
                    pmin = fmin(d - loop)
                    if pmax < dmax and pmin <= dmin:
                        mmin = max(dmin, pmax + D)
                        ans += (dmax - mmin) // D + 1
                    elif pmax >= dmax and pmin > dmin:
                        mmax = min(dmax, pmin - D)
                        ans += (mmax - dmin) // D + 1
                    elif pmax < dmax and pmin > dmin:
                        ans += (dmax - pmax) // D + (pmin - dmin) // D
            print(ans)
                    
        else:
            ans = 0
            g = gcd(-X, D)
            loop = D // g
            for d in range(N + 1):
                if loop <= d:
                    mmax = min(fmax(d), fmin(d - loop) - D)
                else:
                    mmax = fmax(d)
                mmin = fmin(d)
                ans += (mmax - mmin) // D + 1
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[0]*10**8,0
 for x,y,z in sorted((((N-k)*j+~-k)*k//2+k*X//D,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: Accepted

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

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[0]*10**8,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]):
  if c[z]+y<1:
   f[z]=x
  c[z]-=2*y-1
  if c[z]<y:
   r+=x-f[z]+1
print(r)

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[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]):
  if c[z]<2*y:
   r+=x-f[z]+1
  if c[z]+y<1:
   f[z]=x
  c[z]-=2*y-1
print(r)

Submission status: Accepted

Solution code:
N,X,D=map(int,input().split())
r=N*(X!=0)+1
if D:
 f,c,r={},[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]):
  if c[z]<2*y:
    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:
N,X,D=map(int,input().split())
from collections import defaultdict as d
r=N*(X!=0)+1
if D:
 f,c,r=d(int),d(int),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
  f[z]=x if(c[z]+y<1)else f[z]
  c[z]-=2*y-1
print(r)

Submission status: Accepted

Solution code:
N, X, D = map(int, input().split())
if D == 0:
    r = N*(X!=0)+1
else:
    d=dict()
    for k in range(N+1):
        M = (k*X)%D
        F = (k*X)//D + ((k-1)*k)//2 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        if M not in d:
            d[M] = list()
        d[M].append((F,-1))
        d[M].append((L,1))
    r = 0
    for m in d:
        fc=f=0
        for x in sorted(d[m]):
            r+=(x[0]-f+1)*(fc<2)*(x[1]>0)
            fc-=x[1]
            f=(fc==1)*x[0]*(x[1]<0)+f*(x[1]>0 or fc!=1)
print(r)

Submission status: Accepted

Solution code:
N, X, D = map(int, input().split())
if D == 0:
    r = N*(X!=0)+1
else:
    if D < 0:
        X,D=-X,-D
    d=dict()
    for k in range(N+1):
        M = (k*X)%D
        F = (k*X)//D + ((k-1)*k)//2 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        if M not in d:
            d[M] = list()
        d[M].append((F,-1))
        d[M].append((L,1))
    r = 0
    for m in d:
        fc=f=0
        for x in sorted(d[m]):
            r+=(x[0]-f+1)*(fc<2)*(x[1]>0)
            fc-=x[1]
            f=(fc==1)*x[0]*(x[1]<0)+f*(x[1]>0 or fc!=1)
print(r)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

p = dict()
q = dict()

for k in range(n+1):
    temp = k * x % d
    if temp in p.keys():
        #print((k - p[temp]) * x)
        a = (k - p[temp]) * x // d
        L = (k-1)*k//2 + a
        H = (2*n-k-1)*k//2 + a
        q[temp].append([L, H])
    else:
        p[temp] = k
        L = (k-1)*k//2
        H = (2*n-k-1)*k//2
        q[temp] = [[L, H]]

ans = 0

for z in q.values():
    c = - float('inf')
    for a, b in sorted(z):
        if a > c:
            ans += b - a + 1
        elif b > c:
            ans += b - c
        else:
            continue
        c = b

print(ans)

Submission status: Accepted

Solution code:
N, X, D = map(int, input().split())
if D == 0:
    r = N+1
    if X == 0:
        r = 1
    print(r)
else:
    if D < 0:
        X, D = -X, -D
    d = dict()
    for k in range(N+1):
        M = (k*X) % D
        F = (k*X)//D + ((k-1)*k)//2 #(1..k-1)
        L = (k*X)//D + (2*N-k-1)*k//2# (N-k..N-1)
        if M not in d:
            d[M] = list()
        d[M].append((F, 0))
        d[M].append((L, 1))
    r = 0
    for m in d:
        d[m] = sorted(d[m])
        fc = 0
        f = 0
        for x in d[m]:
            if not x[1]:
                fc += 1
                if fc == 1:
                    f = x[0]
            if x[1]:
                fc -= 1
                if fc == 0:
                    r += x[0] - f + 1
    print(r)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

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

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

dic = defaultdict(list)

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

ans = 0
for v in dic.values():
  v.sort()
  ima = -10**100
  for l, r in v:
    if ima < l:
      ans += r - l
      ima = r
    elif r > ima:
      ans += r - ima
      ima = r
print(ans)

Submission status: Accepted

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

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

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

R = {}
R[0] = [[0, 0]]
d, m, l, r = 0, 0, 0, 0

for i in range(N):
  d += (m + X) // D
  m = (m + X) % D
  l += i
  r += N - i - 1
  if m not in R:
    R[m] = [[d + l, d + r]]
  else:
    R[m].append([d + l, d + r])
  
ans = 0
for i in R:
  t = R[i]
  t.sort()
  l, r = t[0]
  for j in range(1, len(t)):
    if r < t[j][0]:
      ans += abs(r - l) + 1
      l, r = t[j]
    else:
      r = max(r, t[j][1])
  ans += abs(r - l) + 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import groupby
def resolve():
    n,a,d=map(int,input().split())
    if(d==0):
        if(a==0): print(1)
        else: print(n+1)
        return
    if(d<0): a,d=-a,-d

    A=[None]*(2*n+2)
    for k in range(n+1):
        L=k*a+k*(k-1)*d//2
        R=k*a+k*(2*n-k-1)*d//2
        r=L%d
        A[2*k]=(r,L//d,0)
        A[2*k+1]=(r,R//d,1)
    A.sort()
    
    ans=0
    for key,iter in groupby(A,lambda x:x[0]):
        now=0
        over=0
        for r,v,q in iter:
            if(q==0):
                if(not over): now=v
                over+=1
            else:
                over-=1
                if(not over): ans+=v-now+1

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n,a,d=map(int,input().split())
    if(d==0):
        if(a==0): print(1)
        else: print(n+1)
        return
    if(d<0): a,d=-a,-d

    D=defaultdict(list)
    for k in range(n+1):
        L=k*a+k*(k-1)*d//2
        R=k*a+k*(2*n-k-1)*d//2
        r=L%d
        D[r].append((L//d,0))
        D[r].append((R//d,1))


    ans=0
    for arr in D.values():
        arr.sort()
        over=0
        now=0
        for v,q in arr:
            if(q==0):
                if(not over): now=v
                over+=1
            else:
                over-=1
                if(not over): ans+=v-now+1

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys

def main():
    n,x,d=map(int,input().split())
    events_map={}
    if d==0:
        if x== 0:
            print(1)
        else:
            print(n+1)
        return
    for k in range(n+1):
        l=(k*x if d > 0 else -k*x)+(k-1)*k//2*abs(d)
        r=(k*x if d > 0 else -k*x)+(n-k+n-1)*k//2*abs(d)
        row=l%abs(d)
        if row not in events_map:
            events_map[row]=[]
        events_map[row].append((l,-1))
        events_map[row].append((r,1))
    ans=0
    for q in events_map.items():
        events=q[1]
        events.sort()
        bal=0
        total=0
        curL=-1
        for event in events:
            if bal==0 and event[1]==-1:
                curL=event[0]
            if bal==1 and event[1] ==1:
                curr=event[0]
                total+=(curr-curL)//abs(d)+1
            bal -= event[1]
        ans+=total
    print(ans)

main()

Submission status: Accepted

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):
    # Xの個数 = d mod Dのとき
    event = []
    for n in range(d,N+1,D):
        # Xがn個
        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
    left_end = 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

answer = sum(F(d) for d in range(min(D,N+1)))
print(answer)

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

(N,X,D) = (int(i) for i in input().split(" "))
mp = {}
if D == 0:
	if X == 0:
		ans = 1
	else:
		ans = N+1
else:
	for i in range(N+1):
		md = (i*X)%D
		if not md in mp:
			mp[md] = []
		k = i*(i-1)//2
		mp[md].append([k+(((i*X)-md)//D),0])
		k = (N*2-i-1)*i//2
		mp[md].append([k+(((i*X)-md)//D)+1,1])
	#print(mp)
	ans = 0
	for k in mp.keys():
		s = sorted(mp[k])
		#print(s)
		md = 0
		bef = 0
		for t in s:
			if md > 0:
				ans += t[0] - bef
			bef = t[0]
			if t[1] == 0:
				md += 1
			else:
				md -= 1
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

Y = dict()

for i in range(n + 1):
	b = -2 * i * X
	r = (n - 1 + n - i) * i // 2
	l = (0 + i - 1) * i // 2
	off = b % (-2 * D)
	l += (b - off) // (-2 * D)
	r += (b - off) // (-2 * D)
	if off in Y:
		Y[off].append((l, r))
	else:
		Y[off] = [(l, r)]

def calc(u):
	pt = dict()
	for l, r in u:
		if l in pt:
			pt[l] += 1
		else:
			pt[l] = 1
		if r + 1 in pt:
			pt[r + 1] -= 1
		else:
			pt[r + 1] = -1
	cur, v = -10 ** 100, 0
	ans = 0
	for k in sorted(pt.keys()):
		if v:
			ans += k - cur
		v += pt[k]
		cur = k
	return ans

print(sum(map(calc, Y.values())))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

ans = 0
if X == D == 0:
    ans = 1
elif X == 0:
    ans = N**2-N*(N+1)//2+1
elif D == 0:
    ans = (N+1)
else:
    if D < 0:
        X = -X
        D = -D
    g = gcd(abs(X), abs(D))
    X //= g
    D //= g
    
    LR = defaultdict(list)
    LR[0].append((0, 0))
    for i in range(1, N+1):
        Li, Ri = (i-1)*i//2, i*N - i*(i+1)//2
        LR[(i*X)%D].append((Li+i*X//D, Ri+i*X//D))
    
    for V in LR.values():
        V.sort()
        lp, rp = V[0]
        for l, r in V[1:]:
            if rp < l:
                ans = (ans + rp-lp+1)
                lp, rp = l, r
            else:
                rp = max(r, rp)
        ans = (ans + rp-lp+1)
print(ans)

Submission status: Accepted

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

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

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

node = []
for i in range(n+1):
    j = n-i
    base = x*(i-j)
    base += 2*d*(i-1)*i//2
    right = (n-i)*i
    if d<0:
        base += 2*d*right
    node.append((base, right))

node.sort()
d = abs(d)
di = {}
mod = 2*d
ans = 0
for base, r in node:
    i = base%mod
    if i in di:
        right_most = di[i]
        if right_most < base:
            ans += r+1
            di[i] = base+2*d*r
        elif base+2*d*r <= right_most:
            continue
        else:
            nxt = base+2*d*r
            ans += (nxt-right_most)//mod
            di[i] = nxt
    else:
        ans += r+1
        di[i] = base+2*d*r

print(ans)

Submission status: Accepted

Solution code:

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
from fractions import gcd

n,x,d = [int(i) for i in readline().split()]

g = gcd(x,d) 

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

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

kind = abs(d//g) #あまりは kind = d//g 種類 

ans = 0



for i in range(min(kind,n+2)):
    res = []
    for j in range(i,n+1,kind):
        res.append([j*x+j*(j-1)//2*d, j*x+(j*n-j*(j+1)//2)*d])
    
    if not res: continue
    
    #print(res)
    res.sort()
    
    q = [res[0][:]]

    for e,f in res:
        while q:
            a,b = q[-1]
            if b < e: break
            else:
                q.pop()
                e,f = a,max(b,f)
        
        q.append([e,f])
    
    #print(q)
    for a,b in q:
        ans += (b-a)//d + 1


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, D = map(int, raw_input().split())
if D == 0:
    if X == 0:
        print 1
    else:
        print N + 1
    exit()
if D < 0:
    X = X + D * (N - 1)
    D = -D
m1 = {}
m2 = {}
m1[0] = D
m2[0] = -D
ans = 1
for i in range(1, N + 1):
    p1 = (X + X + D * (i - 1)) * i / 2
    p2 = (X + D * (N - 1) + X + D * (N - i)) * i / 2
    rem = p1 % D
    if rem in m1:
        ans += max(0, (p2 - max(m1[rem], p1)) / D + 1)
        ans += max(0, (min(p2, m2[rem]) - p1) / D + 1)
    else:
        ans += (p2 - p1) / D + 1
    m1[rem] = p2 + D
    m2[rem] = p1 - D
print ans

Submission status: Accepted

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

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

ranges = {}

for k in range(n+1):
    mod = k * x % d
    l = k * x // d + k * (k-1)//2
    r = k * x // d + k * (2*n-k-1)//2
    if mod not in ranges:
        ranges[mod] = []
    ranges[mod].append((l,-1)) 
    ranges[mod].append((r+1, 1))

ans = 0
    
for mod in ranges:
    lrs = ranges[mod]
    lrs.sort()
    cnt = 0
    last = -1
    for x,y in lrs:
        if cnt == 0:last = x
        cnt += y
        if cnt == 0:
            ans += x - last

print(ans)

Submission status: Runtime Error

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: Runtime Error

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

N, X, D = LI()


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


def main():
    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: Runtime Error

Solution code:
def solve(N, X, D):
    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: Runtime Error

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
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
if d==0:
    ans = n
else:
    if x!=0:
        g = gcd(x,d)
        l = x*d//g
        lx = l//x
        ld = l//d
    d = {} # (要素数, 最大値)
    for i in range(n):
        # iX+sD
        if x!=0:
            ii = i - (i//lx)*lx
        else:
            ii = 0
        jj = (i//lx)*ld
    #     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]
    ans = sum(v[0] for k,v in d.items() if v[1] is not None) + 1
print(ans)

Submission status: Runtime Error

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
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
if x!=0:
    g = gcd(x,d)
    l = x*d//g
    lx = l//x
    ld = l//d
d = {} # (要素数, 最大値)
for i in range(n):
    # iX+sD
    if x!=0:
        ii = i - (i//lx)*lx
    else:
        ii = 0
    jj = (i//lx)*ld
#     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]
ans = sum(v[0] for k,v in d.items() if v[1] is not None)
print(ans+1)

Submission status: Runtime Error

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
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
if x!=0:
    g = gcd(x,d)
    l = x*d//g
    lx = l//x
    ld = l//d
d = {} # (要素数, 最大値)
for i in range(n):
    # iX+sD
    if x!=0:
        ii = i - (i//lx)*lx
    else:
        ii = 0
    jj = (i//lx)*ld
    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]
ans = sum(v[0] for k,v in d.items() if v[1] is not None)
print(ans+1)

Submission status: Runtime Error

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
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
if x!=0:
    g = gcd(x,d)
    l = x*d//g
    lx = l//x
    ld = l//d
d = {i:[0,None] for i in range(n)} # (要素数, 最大値)
for i in range(n):
    # iX+sD
    if x!=0:
        ii = i - (i//lx)*lx
    else:
        ii = 0
    jj = (i//lx)*ld
    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]
ans = sum(v[0] for k,v in d.items() if v[1] is not None)
print(ans+1)