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 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 = {}
if d < 0:
    d = -d
    x = -x
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: 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(1)
    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], 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: Wrong Answer

Solution code:
# F - Sum Difference
INF = 10 ** 60
N, X, D = map(int, input().split())
if D == 0:
    if X == 0:
        print(1)
    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: Wrong Answer

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

Solution code:
import fractions
N, X, D = map(int, input().split())
 
if D==0 and X==0:
    print(1)
    exit()
elif D==0:
    print(N+1)
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()
 
G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+((r-rr)//D if D else 1))
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+((ll-l)//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:
import fractions
N, X, D = map(int, input().split())

if D==0 and X==0:
    print(1)
    exit()
elif D==0:
    print(N+1)
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+((r-rr)//D if D else 1))
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+((ll-l)//D if D else 1))

ans=0
for e in E:
    l,r,c=E[e]
    ans+=c
print(ans)
print(X)
print(D)

Submission status: Wrong Answer

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

if D==0 and X==0:
    print(1)
    exit()
elif D==0:
    print(N+1)
    exit()
elif X==0:
    print(int(N*(N-1)//2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

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

if D==0 and X==0:
    print(int(1))
    exit()
elif D==0:
    print(int(N+1))
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

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

if D==0 and X==0:
    print(1)
    exit()
elif D==0:
    print(N+1)
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

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

if D==0&X==0:
    print(int(1))
    exit()
elif D==0:
    print(int(N))
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

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

if D==0&X==0:
    print(int(1))
    exit()
elif D==0:
    print(int(N+1))
    exit()
elif X==0:
    print(int(N*(N-1)/2+1))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

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

if D==0&X==0:
    print(int(1))
    exit()
elif D==0:
    print(int(N+1))
    exit()
elif X==0:
    print(int(N*(N+1)/2))
    exit()

G=fractions.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=i*X+i*(i-1)*D//2
    r=i*X+i*(2*N-i-1)*D//2
    c=(r-l)//D+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 r>rr:
            #E[k]=(ll,r,(r-ll)//D+1)
            E[k]=(ll,r,cc+(r-rr)//D)
        elif l<ll:
            #E[k]=(l,rr,(rr-l)//D+1)
            E[k]=(l,rr,cc+(ll-l)//D)

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

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

if D == 0 :
  print(N + 1)

else :
  s = X * N + D * N * (N - 1) // 2

  h = defaultdict(lambda: [])
  for i in range(N + 1) :
    a = X * i + D * i * (i - 1) // 2
    b = X * i + D * i * (2 * N - i - 1) // 2
    
    m = 2 * a - s
    M = 2 * b - s
    
    if M < m :
      m, M = M, m
      
    heappush(h[m % (abs(D) * 2)], (m, M))

  D = abs(D)

  ret = 0
  for heap in h.values() :
    u, v = heappop(heap)
    while heap :
      if heap[0][0] <= v :
        v = max(v, heap[0][1])
        heappop(heap)
      else :
        ret += (v - u) // (2 * D) + 1
        u, v = heappop(heap)
        
    ret += (v - u) // (2 * D) + 1

  print(ret)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

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

if D == 0 :
  print(N + 1 - (N + 1) % 2)

else :
  s = X * N + D * N * (N - 1) // 2

  h = defaultdict(lambda: [])
  for i in range(N + 1) :
    a = X * i + D * i * (i - 1) // 2
    b = X * i + D * i * (2 * N - i - 1) // 2
    
    m = 2 * a - s
    M = 2 * b - s
    
    if M < m :
      m, M = M, m
      
    heappush(h[m % (abs(D) * 2)], (m, M))

  D = abs(D)

  ret = 0
  for heap in h.values() :
    u, v = heappop(heap)
    while heap :
      if heap[0][0] <= v :
        v = max(v, heap[0][1])
        heappop(heap)
      else :
        ret += (v - u) // (2 * D) + 1
        u, v = heappop(heap)
        
    ret += (v - u) // (2 * D) + 1

  print(ret)

Submission status: Wrong Answer

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

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

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

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()
    if d == 0:
        if x == 0:
            return 1
        return n + 1

    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:
                if b < u:
                    b = u
            else:
                r += (b-a) // dd + 1
                # print("ab",a,b,(abs(b-a)+dd), dd,r)
                a,b = t,u
        r += (b-a) // dd + 1

    return r % mod


print(main())

Submission status: Wrong Answer

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()
    if d == 0:
        if x == 0:
            return 1
        return n + 1

    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 += (b-a) // dd + 1
                # print("ab",a,b,(abs(b-a)+dd), dd,r)
                a,b = t,u
        r += (b-a) // dd + 1

    return r % mod


print(main())

Submission status: Wrong Answer

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()
    if d == 0:
        if x == 0:
            return 1
        return n

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

Solution code:
INF = 10**30
def solve(n, x, d):
    if d == 0:
        return n+1
    D = {}
    for k in range(n+1):
        l = k*x + (k-1)*k//2*d
        r = k*x + (n*k - k*(k+1)//2)*d
        c = k*x % d
        if not c in D:
            D[c] = []
        l = (l - c) // d
        r = (r - c) // d
        if l > r:
            l, r = r, l
        D[c].append((l, r))
    res = 0
    for v in D.values():
        threshold = -INF
        for l, r in sorted(v):
            l = max(l, threshold)
            res += max(0, r-l+1)
            threshold = max(threshold, r+1)
    return res

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

Submission status: Wrong Answer

Solution code:
INF = 10**20
def solve(n, x, d):
    if d == 0:
        return n+1
    D = {}
    for k in range(n+1):
        l = k*x + (k-1)*k//2*d
        r = k*x + (n*k - k*(k+1)//2)*d
        c = k*x % d
        if not c in D:
            D[c] = []
        l = (l - c) // d
        r = (r - c) // d
        if l > r:
            l, r = r, l
        D[c].append((l, r))
    res = 0
    for v in D.values():
        threshold = -INF
        for l, r in sorted(v):
            l = max(l, threshold)
            res += max(0, r-l+1)
            threshold = max(threshold, r+1)
    return res

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

Submission status: Wrong Answer

Solution code:
INF = 10**20
def solve(n, x, d):
    if d == 0:
        return n+1
    D = {}
    for k in range(1, n+1):
        l = k*x + (k-1)*k//2*d
        r = k*x + (n*k - k*(k+1)//2)*d
        c = k*x % d
        if not c in D:
            D[c] = []
        if l > r:
            l, r = r, l
        D[c].append((l, r))
    res = 0
    for v in D.values():
        threshold = -INF
        for l, r in sorted(v):
            l = max(l, threshold)
            res += max(0, (r-l)//d+1)
            threshold = max(threshold, r+d)
    return res + 1

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

Submission status: Wrong Answer

Solution code:
INF = 10**20
def solve(n, x, d):
    if d == 0:
        return n+1
    D = {}
    for k in range(n):
        l = k*x + (k-1)*k//2*d
        r = k*x + (n*k - k*(k+1)//2)*d
        c = k*x % d
        if not c in D:
            D[c] = []
        if l > r:
            l, r = r, l
        D[c].append((l, r))
    res = 1
    for v in D.values():
        threshold = -INF
        for l, r in sorted(v):
            l = max(l, threshold)
            res += max(0, (r-l)//d+1)
            threshold = max(threshold, r+d)
    return res

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

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

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

Submission status: Wrong Answer

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

    if(d<0): a,d=-a,-d # d>0
    D=defaultdict(list)
    for k in range(n+1):
        q,r=divmod(k*a,d)
        L=q+k*(k-1)//2
        R=q+k*(2*n-k-1)//2
        D[r].append((L,1)) # 1 -> add
        D[r].append((R,2)) # 2 -> remove

    ans=0
    for arr in D.values():
        arr.sort()
        # print(arr)
        over=0
        for v,q in arr:
            if(q==1 and over==0):
                left=v
            over+=1 if(q==1) else -1
            if(over==0):
                ans+=v-left+1
    print(ans)
resolve()

Submission status: Wrong Answer

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

ans = 0

def sum_difference():
    if d < 0:
        D = -d
        X = -x
    else:
        D = d
        X = x
    
    if D == 0:
        if X == 0:
            return 1
        else:
            return N + 1
    
    S1 = [[]]*D
    S2 = [[]]*D        
    for k in range(0,N+1): #条件より、N>=1
        m = k*X % D
        #k個選んだ時の和の最小値、最大値
        Smin = int( k*X + D*( k*(k-1)/2 ))
        Smax = int( k*X + D*( k*(2*N-k-1)/2 ))
        
        if S1[m] == []:
            S1[m] = [Smin]
            S2[m] = [Smax]
        else:
            if Smax < S1[m][-1]:
                S1[m].append(Smin)
                S2[m].append(Smax)
            elif Smin < S1[m][-1] and Smax <= S2[m][-1]:
                S1[m][-1] = Smin
            elif Smin <= S2[m][-1] and S2[m][-1] < Smax:
                S2[m][-1] = Smax
            elif S2[m][-1] < Smin:
                S1[m].append(Smin)
                S2[m].append(Smax)
    
    cnt = 0
    for mm in range(D):
        for c1,c2 in zip(S1[mm],S2[mm]):
            cnt+= (c2-c1)//D +1
    
    return int(cnt)
    
ans = sum_difference()
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import defaultdict

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

if D == 0:
    if X == 0:
        ans = 0
    else:
        ans = N + 1
else:
    # 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: Wrong Answer

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:
    if X==0:
        print(1)
    else:
        print(N+1)
    exit()
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: Wrong Answer

Solution code:
from collections import 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()
        l,r = q[0]
        for i in range(len(q)):
            a,b = q[i]
            if a<=r:
                r = max(r,b)
            else:
                ans += (r-l)//D+1
                l = a
                r = b
        ans += (r-l)//D+1

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

Submission status: Wrong Answer

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
                    q.appendleft([a2,b2])
            else:
                ans += (b1-a1)//D+1

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from operator import itemgetter

def solve(N, X, D):
    if D < 0:
        D = -D
        X = -X
    elif D == 0:
        return N + 1

    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
    return ans


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

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, X, D = list(map(int, sys.stdin.buffer.readline().split()))
if D < 0:
    X += (N - 1) * D
    D = -D

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

# 差じゃなくて高橋くんが作れる数だけ考える
# lr[k]: mod D が k になる数のどっからどこまで作れるか
ranges = defaultdict(list)
for n in range(N + 1):
    # 選ぶ数を決めると、選ぶ数の合計 mod D が決まる
    # 選ぶ数の合計を X*n + D*y とすると
    # d を使う数は最小で 0 から n-1 までの合計
    y_min = (n - 1) * n // 2
    # d を使う数は最大で N-1 + N-2 + ... + N-n == N*n - (1 から n までの合計)
    y_max = N * n - (n + 1) * n // 2
    k = X * n % D
    ranges[k].append((X * n // D + y_min, X * n // D + y_max + 1))


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


def count(lr):
    if len(lr) == 1:
        l, r = lr[0]
        return r - l

    # mod D で分けてるから座圧できる
    flatten = list(itertools.chain.from_iterable(lr))
    ranks = compress(flatten, origin=1)
    orig = [0] * (max(ranks) + 1)
    for r, f in zip(ranks, flatten):
        orig[r] = f

    imos = [0] * (len(ranks) + 10)
    for l, r in zip(ranks[::2], ranks[1::2]):
        imos[l] += 1
        imos[r] -= 1
    cum = cumsum(imos)

    ret = 0
    for i in range(len(cum) - 1):
        if cum[i] == 0 and cum[i + 1] > 0:
            left = orig[i + 1]
        if cum[i] > 0 and cum[i + 1] == 0:
            ret += orig[i + 1] - left
    return ret


ans = 0
i = 0
for lr in ranges.values():
    ans += count(lr)
    i += 1
print(ans)