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

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():
    if D < 0:
      min_num = min(k, key=lambda x:x[1])[1]
      max_num = max(k, key=lambda x:x[0])[0]
      abs_min_num = abs(min_num)
      abs_max_num = abs(max_num)
      num_lis = np.zeros((abs_max_num+abs_min_num+1))
      for l in k:
        num_lis[l[1]+abs_min_num:l[0]+abs_min_num+1] += 1
    else:
      min_num = min(k, key=lambda x:x[0])[0]
      max_num = max(k, key=lambda x:x[1])[1]
      abs_min_num = abs(min_num)
      abs_max_num = abs(max_num)
      num_lis = np.zeros((abs_max_num+abs_min_num+1))
      for m in k:
        num_lis[m[0]+abs_min_num:m[1]+abs_min_num+1] += 1
    ans += np.count_nonzero(num_lis > 0)
    
  print(ans)

Submission status: Runtime Error

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

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 range(d):
  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, xs[i - 1], l)
  
  #print(table, xs)
#print(a)
print(res)

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
N, X, D = map(int, input().split())
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: Runtime Error

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

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

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

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

dic={}

ans=0
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: Runtime Error

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

dic={}

ans=0
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
    print(l,r,idx)
    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: Runtime Error

Solution code:
import sys
from math 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: Runtime Error

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

    N, x, d = map(int, input().split())
    
    assert d != 0
    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: Runtime Error

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

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 = d//g
hani = [[] for _ in range(n)]
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):
    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: Runtime Error

Solution code:
import math
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 = math.gcd(d, x)
mod = d//g
hani = [[] for _ in range(n)]
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):
    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: Runtime Error

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



n, x, d = LI()
D = defaultdict(list)
for i in range(n + 1):
    a = i * x
    L = i * (i - 1) // 2
    R = (2 * n - i - 1) * i // 2
    D[a % d] += [(a // d + L, a // d + R)]


ans = 0
for L in D.values():
    L.sort()
    now = -INF
    for l, r in L:
        if r <= now:
            continue
        elif l > now:
            ans += r - l + 1
        else:
            ans += r - now
        now = r


print(ans)

Submission status: Runtime Error

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(tmp)
    exit()
elif d == 0:
    print(tmp)
    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], key = itemgetter(1))
    right = -10**18
    for j in memo[i]:
        l, r = j
        ans += min(r - l, r - right)
        right = r
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

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

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

else:
    # sが何通りあるかを求める
    
    # dを正にする
    if d < 0: d, x = -d, -x

    # d,xを互いに素にする   
    g = gcd(d, abs(x))
    d, x =  d//g, x//g
    
    # s=k*x+c*d
    # cは最小で0からk-1の和、最大でn-kからn-1の和
    # kを固定するとs//dは1ずつの単調増加なので、最小と最大で個数が分かる

    # sはs%d=k*x%dなので、それで分類する
    # →klistをk*x%dでソート
    klist = list(range(n + 1))
    klist.sort(key=lambda k: (k*x%d, k))

    # kを固定し、cの最小・最大を求め、加算していく
    ans = 0

    # 1つ前の値を保持
    pmin, pmax = 1, 0
    pmd = -1
    for k in klist:
        # s//dの最小・最大・s%d
        tmin = (k * x + (k - 1) * k // 2 * d) // d
        tmax = (k * x + (2 * n - k - 1) * k // 2 * d) // d
        tmd = k*x%d

        # s%dが前と同じ　かつ
        # s//dの最小<=前の最大　かつ　s//dの最大>=前の最小のとき
        # 最大・最小を更新
        if tmd == pmd and tmin <= pmax and tmax >= pmin:
            pmin, pmax = min(pmin, tmin), max(pmax, tmax)
        else:
            ans += pmax - pmin + 1
            pmin, pmax = tmin, tmax
        pmd = tmd
        #print(k, l, r, pl, pr, ans)
    
    ans += pmax - pmin + 1
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#写経
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#　縦に並んだ入力を受け取りたい時はread().split()をとる zip(m,m)で分ける
N,U,V = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

#tree の受け取り：頂点の数＋１のリストを用意して、それぞれの頂点が辺を貼るnodeを全てリストに保存
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#全探索して入力頂点からの距離を返す
#全ての頂点に対して、
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:#頂点から辺が貼られている頂点に対して
            if dist[w] >= 0:#すでに訪れている
                continue
            dist[w] = dw#訪れてないなら更新
            stack.append(w)
    return dist

DU,DV = dfs(U),dfs(V)
 
answer = 0
#元の場所以外の全ての頂点を探索する
for u,v in zip(DU[1:],DV[1:]):
    if u < v:#逃げる方が先につく中で最短を探す
        x = v - 1
        if answer < x:
            answer = x
 
print(answer)

Submission status: Runtime Error

Solution code:
# F - Sum Difference
INF = 10 ** 60
N, X, D = map(int, input().split())
if D == 0:
    if X == 0:
        print(0)
    else:
        print(N + 1)
else:
    # Sの要素を数列からi個選ぶ
    mp = {}
    for i in range(N + 1):
        s = X * i
        l = i * (i - 1) / 2
        r = l + i * (N - i)
        s += l * D
        r -= l
        key = (s % D + D) % D
        if key in mp:
            mp[key].append([s, r])
        else:
            mp[key] = [[s, r]]
            
ans = 0
for key, value in mp.items():
    m = len(value)
    for i in range(m):
        value[i][0] = (value[i][0] - key) / D
        
    ev = []
    for i in range(m):
        ev.append((value[i][0], 1))
        ev.append((value[i][0] + value[i][1] + 1, -1))
    ev.sort()
    
    cnt = 0
    pre = -INF
    for e in ev:
        length = e[0] - pre
        if cnt > 0:
            ans += length
        cnt += e[1]
        pre = e[0]
    
print(int(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, x, d = [int(item) for item in input().split()]
range_in_kXmodD = dict() 
for i in range(0, n+1):
    kXmodD = i * x % d
    start = (i * x) // d + i * (i - 1) // 2
    end = (i * x) // d + i * (n - i + n - 1) // 2 + 1
    if kXmodD not in range_in_kXmodD:
        range_in_kXmodD[kXmodD] = []
    range_in_kXmodD[kXmodD].append((start, 1))
    range_in_kXmodD[kXmodD].append((end, -1))

ans = 0
for key in range_in_kXmodD.keys():
    range_in_kXmodD[key].sort()
    ret = 0
    cnt = 0
    prev = None 
    for val, c in range_in_kXmodD[key]:
        if prev != None and cnt > 0:
            ret += val - prev
        cnt += c
        prev = val
    ans += ret

print(ans)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,x,d = LI()
    c = collections.defaultdict(list)
    ad = n * (n-1) // 2 * d + x * n
    # print(ad)
    dd = abs(d)*2
    for i in range(n+1):
        u = ad - (x * i + ((i-1) * i // 2) * d) * 2
        k = ad - (x * i + ((n-1 + n-i) * i // 2) * d) * 2
        # print("iku",i,k,u)
        if k > u:
            k,u = u,k
        c[k%dd].append((k,u))

    r = 0
    for k, v in c.items():
        v.sort()
        # print(k,v)
        a,b = v[0]
        for t,u in v[1:]:
            if t <= b:
                b = u
            else:
                r += (abs(b-a)+dd) // dd
                # print("ab",a,b,(abs(b-a)+dd), dd,r)
                a,b = t,u
        r += (abs(b-a)+dd) // dd

    return r


print(main())

Submission status: Runtime Error

Solution code:
import fractions

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

"""

X+0D
X+1D
X+2D
...
X+(N-1)D

からとってくる

aX + bD

aX中にlcmがtこあるとき、 newa = (aX-t*lcm) // X = a - t*lcm//X
newl += lcm*t // D

で、aX > lcm(X,D)だったらaをへらして?の範囲をうしろにずらす
各aについて計算量はO(1)

3,4,2のとき
4
6
8
lcm = 4

0,4,6,8,10,12,14,18

XD両方負だと問題なし
Dが負の時 >> 大事なのは aXを変換できるならDにする>aを減らす
?X > !Dにする

X  D
3 -3

X + 0D = 3
X + 1D = 0

0X = 0
1X + 

lcm = 3
なので,0は X+-1Dに変換可能

"""

l = [ [] for i in range(N+1)]
r = [ [] for i in range(N+1)]
lcm = X*D // fractions.gcd(X,D)


bl = 0
br = 0


for a in range(N+1):


    if a > 0:
        bl += a-1
        br += N-a

    #print (bl,br)

    t = (a*X) // lcm
    #print (a,t*lcm//X)
    a -= t*lcm // X

    l[a] .append(bl + lcm*t // D)
    r[a] .append(br + lcm*t // D)

ans = 0


for a in range(N+1):

    now = 0
    nl = 0
    lind = 0
    rind = 0
    l[a].sort()
    r[a].sort()
    
    for i in range(2 * len(l[a])):

        if rind == len(r[a]) or (lind != len(l[a]) and l[a][lind] <= r[a][rind]):
            if now == 0:
                nl = l[a][lind]
            now += 1
            lind += 1
        else:
            now -= 1
            if now == 0:
                ans += r[a][rind] - nl + 1
            rind += 1
        
 

#print (l)
#print (r)
print (ans)

Submission status: Runtime Error

Solution code:
import fractions

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

"""

X+0D
X+1D
X+2D
...
X+(N-1)D

からとってくる

aX + bD

aX中にlcmがtこあるとき、 newa = (aX-t*lcm) // X = a - t*lcm//X
newl += lcm*t // D

で、aX > lcm(X,D)だったらaをへらして?の範囲をうしろにずらす
各aについて計算量はO(1)

3,4,2のとき
4
6
8
lcm = 4

0,4,6,8,10,12,14,18

XD両方負だと問題なし
Dが負の時 >> 大事なのは aXを変換できるならDにする>aを減らす

"""

l = [ [] for i in range(N+1)]
r = [ [] for i in range(N+1)]
lcm = X*D // fractions.gcd(X,D)


bl = 0
br = 0


for a in range(N+1):


    if a > 0:
        bl += a-1
        br += N-a

    #print (bl,br)

    t = (a*X) // lcm
    #print (a,t*lcm//X)
    a -= t*lcm // X

    l[a] .append(bl + lcm*t // D)
    r[a] .append(br + lcm*t // D)

ans = 0

for a in range(N+1):

    now = 0
    nl = 0
    lind = 0
    rind = 0
    
    for i in range(2 * len(l[a])):

        if rind == len(r[a]) or (lind != len(l[a]) and l[a][lind] <= r[a][rind]):
            if now == 0:
                nl = l[a][lind]
            now += 1
            lind += 1
        else:
            now -= 1
            if now == 0:
                ans += r[a][rind] - nl + 1
            rind += 1
        
        

#print (l)
#print (r)
print (ans)

Submission status: Runtime Error

Solution code:
a,b,c=map(int,input().split())
seq=[]
for i in range(a):
  seq.append(b)
  b+=c
if 0 in seq:
  print(int(2**a/2))
else:
  print(2**a)

Submission status: Runtime Error

Solution code:
a,b,c=map(int,input().split())
seq=[]
for i in range(a):
  seq.append(b)
  b+=c
if 0 in seq:
  print(2**a/2)
else:
  print(2**a)

Submission status: Runtime Error

Solution code:
from fractions import gcd
from collections import defaultdict

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

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

AN = X + D * (N - 1)

intervals_dict = defaultdict(list)
for k in range(N + 1):
    start = k * (2 * X + (k - 1) * D) // 2
    end = k * (2 * AN - (k - 1) * D) // 2

    intervals_dict[start % D].append((start // D, end // D +1))

ans = 0
for k, v in intervals_dict.items():
    v.sort()

    current_stop = -float("inf")
    for start, stop in v:
        ans += max(stop, current_stop) - max(start, current_stop) 
        current_stop = max(current_stop, stop)

print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

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

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
    for r in range(start, end + D, D):
        ans_set.add(r)

print(len(ans_set))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
dp = [[{} for _ in range(W)] for _ in range(H)]
dp[0][0][D[0][0]] = 0
for h in range(H):
    for w in range(W):
        for v in dp[h][w]:
            if w != W-1:
                v1 = v+D[h][w+1]
                v2 = v-D[h][w+1]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h][w+1][v1] = 0
                dp[h][w+1][v2] = 0
            if h != H-1:
                v1 = v+D[h+1][w]
                v2 = v-D[h+1][w]
                if v1<0:
                    v1 *= -1
                if v2<0:
                    v2 *= -1
                dp[h+1][w][v1] = 0
                dp[h+1][w][v2] = 0
ans = min(dp[H-1][W-1])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

inf = 10**30
N,X,D = II()

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

kukan = []
for i in range(N+1):
    kukan.append([i*X+(i*(i-1)//2)*D, i*X+(N*(N-1)//2-(N-i)*(N-i-1)//2)*D, (i*X)%D])
kukan.sort(key=lambda x:(x[2],x[0]))

div,d_min,d_max = inf,inf,inf
ans = 0
for k in kukan:
    if k[2]!=div:
        if d_min!=inf:
            ans += (d_max-d_min)//D + 1
        d_min,d_max,div = k[0],k[1],k[2]
    else:
        if k[0]>d_max:
            ans += (d_max-d_min)//D + 1
            d_min,d_max = k[0],k[1]
        else:
            d_max = k[1]
ans += (d_max-d_min)//D + 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
N,X,D = map(int,input().split())
d = defaultdict(list)
if D<0:
    D *= -1
    X *= -1

if D != 0:
    for m in range(N+1):
        if m==0:
            a = 0
            b = 0
        else:
            a = X*m+(m*(m-1)*D)//2
            b = X*m+(m*(2*N-m-1)*D)//2
        d[a%D].append([a,b])


    ans = 0
    for k in d:
        q = d[k]
        q.sort()
        q = deque(q)
        while q:
            a1,b1 = q.popleft()
            if q:
                a2,b2 = q.popleft()
                if a2 <= b1:
                    q.appendleft([a1,b2])
                else:
                    ans += (b1-a1)//D+1
                    l.append([a1,b1])
                    q.appendleft([a2,b2])
            else:
                ans += (b1-a1)//D+1

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

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
N,X,D = map(int,input().split())
d = defaultdict(list)
if D<0:
    D *= -1
    X *= -1

for m in range(N+1):
    if m==0:
        a = 0
        b = 0
    else:
        a = X*m+(m*(m-1)*D)//2
        b = X*m+(m*(2*N-m-1)*D)//2
    d[a%D].append([a,b])


ans = 0
for k in d:
    q = d[k]
    q.sort()
    q = deque(q)
    while q:
        a1,b1 = q.popleft()
        if q:
            a2,b2 = q.popleft()
            if a2 <= b1:
                q.appendleft([a1,b2])
            else:
                ans += (b1-a1)//D+1
                l.append([a1,b1])
                q.appendleft([a2,b2])
        else:
            ans += (b1-a1)//D+1


print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import itemgetter

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

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

ans = 0
for v in s.values():
    if not v: continue
    v.sort()
    a, b = v[0]
    for x, y in v[1:]:
        if b < x:
            ans += b - a
            a, b = x, y
        else:
            b = max(b, y)
    ans += b - a

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import itemgetter

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

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

ans = 0
for v in s.values():
    v.sort()
    a, b = v[0]
    for x, y in v[1:]:
        if b < x:
            ans += b - a
            a, b = x, y
        else:
            b = max(b, y)
    ans += b - a

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a: int, b: int)->int:
    if a < b:
        a, b = b, a
    return gcd(b, a % b) if b else a


def sum_seq1(l: int, r: int)->int:
    if r < l:
        return 0
    return r*(r+1) // 2 - l*(l-1) // 2


def sum_difference(N: int, X: int, D: int)->int:
    if D == 0:
        if X == 0:
            return 1
        return N+1

    # D != 0
    D = abs(D)

    g = gcd(X, D)
    a, b = D // g, -X // g

    if a < 0:
        a *= -1
        b *= -1

    i_range = [(float('inf'), -float('inf'))] * (N+1)

    ans = 0
    for k in range(N+1):
        kl, kr = i_range[k]
        nl = sum_seq1(0, k-1)
        nr = sum_seq1(N-k, N-1)
        # print('k: ({}, {}), n: ({}, {})'.format(kl, kr, nl, nr))

        if k+a <= N:
            i_range[k+a] = (b+min(kl, nl), b+max(kr, nr))

        if kr == -float('inf'):
            ans += nr - nl + 1
        elif kr < nl or nr < kl:
            ans += nr - nl + 1
        elif nl <= kl and kr <= nr:
            ans += (nr-nl+1) - (kr-kl+1)
        elif kl <= nl:
            ans += max(0, nr-kr)
        else:
            ans += kl-nl

    return ans


if __name__ == "__main__":
    N, X, D = map(int, input().split())
    ans = sum_difference(N, X, D)
    print(ans)

Submission status: Runtime Error

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

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 = {}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if kl <= dic[kmod][2]:
      rl -= ((dic[kmod][2] - kl) // d + 1)
    if kl <= dic[kmod][1]:
      rl += ((dic[kmod][1] - kl) // d)
    dic[kmod] = [dic[kmod][0] + rl, kr]
  else:
    dic[kmod] = [rl, kl, kr]

print(sum([i[0] for i in dic.values()]) + 1)

Submission status: Runtime Error

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 = {}
for k in range(1, n + 1):
  left = (k - 1) * k // 2
  right = (2 * n - k - 1) * k // 2
  rl = right - left + 1
  kx = k * x
  kl = kx + left * d
  kr = kx + right * d
  kmod = kx % d
  if kmod in dic:
    if kl <= dic[kmod][1]:
      rl -= ((dic[kmod][1] - kl) // d + 1)
    dic[kmod] = [dic[kmod][0] + rl, kr]
  else:
    dic[kmod] = [rl, kr]

dic[0][0] += 1
print(sum([i[0] for i in dic.values()]))

Submission status: Runtime Error

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)]

def main():
    n, x, d = MI()
    ad = abs(d)
    # 数列からk個選んだ和の範囲をkx mod dで分けて記録
    range_by_mod = [[None, None] for _ in range(ad)]
    ans = 0
    for k in range(n + 1):
        l = (k * (k - 1) * d // 2 + k * x) // ad
        r = ((2 * n - k - 1) * k * d // 2 + k * x) // ad
        if l > r: l, r = r, l
        pl, pr = range_by_mod[k * x % ad]
        if pl == None:
            range_by_mod[k * x % ad] = [l, r]
        else:
            if l <= pr:
                range_by_mod[k * x % ad][1] = r
            else:
                ans += pr - pl + 1
                range_by_mod[k * x % ad] = [l, r]
        #print(k, l, r, k * x % ad, ans)
        #print(range_by_mod)
    for l, r in range_by_mod:
        if l == None: continue
        ans += r - l + 1
    print(ans)

main()