Problem:


Score: 500 points

Problem Statement

You are the top spy of AtCoder Kingdom. To prevent the stolen secret from being handed to AlDebaran Kingdom, you have sneaked into the party where the transaction happens.

There are N attendees in the party, and they are given attendee numbers from 1 through N. The height of Attendee i is A_i.

According to an examination beforehand, you know that a pair of attendees satisfying the condition below will make the transaction.

The absolute difference of their attendee numbers is equal to the sum of their heights.

There are \frac{N(N-1)}{2} ways to choose two from the N attendees and make a pair. Among them, how many satisfy the condition above?

P.S.: We cannot let you know the secret.

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the number of pairs satisfying the condition.

Sample Input 1

6
2 3 3 1 3 1

Sample Output 1

3

A_1 + A_4 = 3, so the pair of Attendee 1 and 4 satisfy the condition.

A_2 + A_6 = 4, so the pair of Attendee 2 and 6 satisfy the condition.

A_4 + A_6 = 2, so the pair of Attendee 4 and 6 satisfy the condition.

No other pair satisfies the condition, so you should print 3.

Sample Input 2

6
5 2 4 2 8 8

Sample Output 2

0

No pair satisfies the condition, so you should print 0.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

22



Sample input:
6
2 3 3 1 3 1


Sample output:
3

Submission status: Accepted

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

ans = 0
start_idx = [0] * N
for i, a in enumerate(A):
    if i+1+a < N:
        start_idx[i+1+a] += 1
    if i-a+1 >= 0:
        ans += start_idx[i-a+1]

print(ans)

Submission status: Accepted

Solution code:
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys,heapq,math
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n=int(data())
    A=list(mdata())
    d1=dd(int)
    d2=dd(int)
    for i in range(n):
        if i+1+A[i]<n:
            d1[i+1+A[i]]+=1
        if i+1-A[i]>1:
            d2[i+1-A[i]]+=1
    ans=0
    for i in d1:
        ans+=d1[i]*d2[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
li = list(map(int,input().split()))	
di = {}
count = 0
for i in range(N):
    if str((i+1)-li[i]) in di.keys(): 
        count += di[str((i+1)-li[i])]
    if str(i+1+li[i]) in di.keys(): 
        di[str(i+1+li[i])] += 1
    else:
        di[str(i+1+li[i])] = 1
print(count)

Submission status: Accepted

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

p = {}
q = {}
for i in range(n):
  pp = a[i]+i+1
  if pp in p:
    p[pp] += 1
  else:
    p[pp] = 1
  qq = -(a[i]-(i+1))
  if qq in q:
    q[qq] += 1
  else:
    q[qq] = 1
ans = 0
for kp,vp in p.items():
  if kp in q:
    vq = q[kp]
    ans += vp*vq
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

from collections import defaultdict
d = defaultdict(int)
ans = 0

for i in range(n):
    ans += d[i-a[i]]
    d[a[i]+i] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
plus = [0] * n
minus = [0] * n
for i in range(n):
    plus[i] = i + a[i]
    minus[i] = i - a[i]
# print(plus)
# print(minus)

d = {}
for i in range((n)):
    if minus[i] in d:
        d[minus[i]] += 1
    else:
        d[minus[i]] = 1
# print(d)

ans = 0
for i in range(n):
    if plus[i] in d:
        ans += d[plus[i]]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))
S = [-A[i] for i in range(N)]

for i in range(N):
    A[i] += i
    S[i] += i
D = {}
for i in range(N):
    if A[i] in D:
        D[A[i]][0] += 1
    else:
        D[A[i]] = [1, 0]
    if S[i] in D:
        D[S[i]][1] += 1
    else:
        D[S[i]] = [0, 1]
cnt = 0
for i in D:
    cnt += D[i][0] * D[i][1]
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(val) for val in input().split()]
mp = dict()
ans = 0
for i in range(n):
    addval = a[i] + (i + 1)
    subval = (i + 1) - a[i]
    if subval in mp.keys():
        ans += mp[subval]
    mp[addval] = mp.get(addval, 0) + 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
a=list(map(int,input().split()))
num1=[0]*n
num2=[0]*n
for i in range(n):
    num1[i]=i+1+a[i]
    num2[i]=i+1-a[i]
num2_sort=sorted(list(set(num2)))
num2_set=set(num2)
num2_cnt=[0]*len(num2_sort)
for i in range(n):
    b=bisect_left(num2_sort,num2[i])
    num2_cnt[b]+=1
ans=0
for i in range(n):
    if num1[i] in num2_set:
        c=bisect_left(num2_sort,num1[i])
        ans+=num2_cnt[c]
    d=bisect_left(num2_sort,num2[i])
    num2_cnt[d]-=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
li1 = [0]*(n)
li2 = [0]*n
for i in range(n):
    if a[i]+i<n:
        li1[a[i]+i]+=1 
    if 0<=i-a[i]<n:
        li2[-a[i]+i]+=1
for i in range(n):
    ans+=li1[i]*li2[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

minus = []
plus = []
for i in range(len(A)):
    minus.append(A[i]-(i+1))
    plus.append(-A[i]-(i+1))
minus.sort()
plus.sort()
#print (minus)
#print (plus)
minus.append(INF)
plus.append(INF)
i=0
j=0
ans=0
while(i!=N and j!=N):
    
    if minus[i] < plus[j]:
        i+=1
    elif minus[i] > plus[j]:
        j+=1
    else:
        ci = 1
        cj = 1
        #print (minus[i],plus[j],ans,i,j)
        while(minus[i+1] == minus[i]):
            i+=1
            ci += 1
        while(plus[j+1] == plus[j]):
            j+=1
            cj += 1
        i+=1
        j+=1
        ans += ci*cj
    
print (ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())

border = N * 2

A = list(map(int, input().split()))

b = [A[0] + 1]

C = [0] * (border + 1)

ans = 0

for i, a in enumerate(A, 1):
    if 0 <= i - a <= border:
        ans += C[i - a]
    if i + a <= border:
        C[i + a] += 1
    #br = bisect.bisect_right(b, i - a)
    #bl = bisect.bisect_left(b, i - a)
    #ans += br - bl
    #b.index(bl, i + a)

print(ans)

Submission status: Accepted

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

count=0
wa={}
for j in range(1,n):
  if j+a[j-1] not in wa:
    wa[j+a[j-1]]=1
  else:
    wa[j+a[j-1]]+=1
  
  sa=j+1-a[j]
  if sa in wa:
    count+=wa[sa]

print(count)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = [a-i for i, a in enumerate(A)]
S = Counter(A)
ans = 0
for i, a in enumerate(A):
    ans += S[-2*i-a]
print(ans)

Submission status: Accepted

Solution code:


def solve():
    left = {}
    right = {}
    for i in range(n):
        r = - a[i] + (i + 1)
        l = a[i] + (i + 1)
        if not str(r) in right:
            right[str(r)] = 1
        else:
            right[str(r)] += 1
        if not str(l) in left:
            left[str(l)] = 1
        else:
            left[str(l)]+= 1
    ans = 0
    for i in range(n):
        ii = str(i)
        if ii in right and ii in left:
            ans += right[ii] * left[ii]
    print(ans)
    return


n = int(input())
a = [int(s) for s in input().split(" ")]
solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

def resolve():
    n = int(input())
    a = list(map(int, input().split()))

    b = [a[i] + i + 1  for i in range(n)]
    c = {}
    for i in range(n):
        cc = a[i] - i - 1
        if cc not in c:
            c[cc] = []
        c[cc].append(i)
    ans = 0

    for i in range(n):
        bb = -b[i]
        if bb not in c:
            continue
        idx = bisect_left(c[bb], i)
        ans += len(c[bb]) - idx
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
N = I()
a = LI()
s = [0]*N
for i in range(N):
    if i-a[i]+1>=0:
        s[i-a[i]+1] += 1
ans = 0
for i in range(N):
    start = i+a[i]+1
    if start<N:
        ans += s[start]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
r=[[] for _ in range(n)]
l=[[] for _ in range(n)]
for i in range(n):
	if i+a[i]<n:
		r[i+a[i]].append(i)
	if i-a[i]>=0:
		l[i-a[i]].append(i)
cnt=0
for i in range(n):
	cnt+=len(l[i])*len(r[i])
print(cnt)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A1=[]
A2=[]
for i in range(N):
  A1.append(i+1+A[i])
  A2.append(i+1-A[i])
A1.sort()
#A2.sort()
ans=0
for i in range(N):
  ai=A[i]
  i+=1
  ans+=bisect.bisect_right(A1,i-ai)-bisect.bisect_left(A1,i-ai)
  #ans+=bisect.bisect_right(A2,i+ai)-bisect.bisect_left(A2,i+ai)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = []
T = []
for i in range(1,N+1):
    S.append(i+A[i-1])
    T.append(i-A[i-1])

L = []
for i in range(N):
    L.append(S[i]-1)

from collections import Counter
M = Counter(L)
out = 0
for i in range(N):
    if (T[i]-1>=0)and(len(L)-1>=T[i]-1):
        out += M[T[i]-1]
        if T[i]==S[i]:
            out += -1
print(out)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n = inp()
x = ip()
ctr = 0
a = [i+x[i] for i in range(n)]
b = [i-x[i] for i in range(n)]

dt1 = {} 
for i in a: dt1[i] = dt1.get(i,0)+1
dt2 = {} 
for i in b: dt2[i] = dt2.get(i,0)+1

for i in dt1:
    if i in dt2:
        ctr += dt1[i]*dt2[i]
print(ctr)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = solve(n, a)
    print(ans)


def solve(n, a):
    x = {}
    for i in range(n):
        tmp = i - a[i] + 1
        if tmp >= 0:
            if tmp in x:
                x[tmp] += 1
            else:
                x[tmp] = 1
    ans = 0
    for i in range(n):
        tmp = a[i] + i + 1
        if tmp in x:
            ans += x[tmp]
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l1 = []
l2 = []

for i, h in enumerate(a):
    l1.append(i + h+1)
    l2.append(i - h+1)

c1 = Counter(l1)
c2 = Counter(l2)

cnt = 0

for h in (c1.keys() | c2.keys()):
    if h in c1.keys() and h in c2.keys():
        cnt += c1[h] * c2[h]

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = Counter([e+i+1 for i,e in enumerate(a)])
    c = Counter([i+1-e for i,e in enumerate(a) if i+1-e > 1])
    ans = 0
    for i in c:
        ans += b[i] * c[i]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = [i + ai for i, ai in enumerate(a)]
c = Counter(i - ai for i, ai in enumerate(a))
ans = 0
for bi in b:
    ans += c[bi]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
sa = [0]*n
wa = [0]*n

ans = 0
for i in range(n):
    sa[i] = a[i]-i
    wa[i] = a[i]+i
b = Counter(wa)
c = Counter(sa)
    
for i in b:
    ans += b[i]*c[-i]
            
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
dic = defaultdict(int)
for i, a in enumerate(A):
    x = a - i
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1

answer = 0
for i, a in enumerate(A):
    y = a + i
    answer += dic[-y]
    x = a - i
    dic[x] -= 1

print(answer)

Submission status: Accepted

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

# add = [None] * (N+1)
# sub = [None] * (N+1)

from collections import defaultdict
add = defaultdict(int)
sub = defaultdict(int)

ans = 0
for i in range(N):
    ans += add[i+1 - A[i]] 
    ans += sub[i+1 + A[i]] 
    add[i+1 + A[i]] += 1
    sub[i+1 - A[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = {}
s = set()
ans = 0
d[a[0]] = 1
s.add(a[0])
for i in range(1, n):
    if i-a[i] in s:
        ans += d[-a[i]+i]
    
    if a[i]+i in s:
        d[a[i]+i] = d[a[i]+i]+1
    else:
        s.add(a[i]+i)
        d[a[i]+i] = 1
print(ans)

Submission status: Accepted

Solution code:
def main():

    from collections import Counter
    n = int(input())
    l = list(map(int,input().split()))

    l1 = []
    for i in range(n):
        l1.append(i-l[i])

    c = Counter(l1)
    count = 0
    for i in range(n-1):
        a = 2*i-l1[i]
        if a in c:
            count += c[a]
    print(count)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans_list = [0] * N
total = 0
for i in range(N):
    if i + A[i] < N:
        ans_list[i + A[i]] += 1
    if i - A[i] >= 0:
        total += ans_list[i - A[i]]

print(total)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = []
C = []
D = [0]*N
E = [0]*N
t = 0
for i in range(N):
    B.append(i+1-A[i])
    C.append(i+1+A[i])
for i in range(N):
    if B[i] > 0 and B[i] <= N:
        D[B[i]-1] += 1
    if C[i] <= N:
        E[C[i]-1] += 1
for i in range(N):
    t += D[i]*E[i]
print(t)

Submission status: Accepted

Solution code:
n = int(input())
As = list(map(int, input().split()))

as1 = [-(a+i) for i,a in enumerate(As)]
as2 = [a-i for i,a in enumerate(As)]

from collections import defaultdict
d1 = defaultdict(int)
d2 = defaultdict(int)
cnt = 0

for a1,a2 in zip(as1,as2):
    d1[a1] += 1
    d2[a2] += 1
# print(d1,d2)

for k in d1.keys():
    cnt += d1[k]*d2[k]
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))

ret = 0
my_dict = dict()

for i in range(1, len(a_list)):
    diff = a_list[i] + a_list[0] - i
    if diff in my_dict:
        my_dict[diff].append(i)
    else:
        my_dict[diff] = [i]
    if diff == 0:
        ret += 1

for i in range(1, len(a_list)):
    diff = a_list[i] - a_list[0] + i
    if (-diff) in my_dict:
        tmp_list = my_dict[-diff]
        while len(tmp_list) >= 1:
            if tmp_list[0] <= i:
                tmp_list.pop(0)
            else:
                break
        ret += len(tmp_list)

print(ret)

Submission status: Accepted

Solution code:
import bisect as bi
import collections as cc
I=lambda:list(map(int,input().split()))
d=cc.defaultdict(int)
n,=I()
l=I()
ans=0
for i in range(n):
    d[l[i]+i]+=1
    ans+=d[i-l[i]]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
no = [i for i in range(N)]
A = list(map(int, input().split()))

no_minus_height = {}
#no_plus_height = {}
total = 0
for i in range(N-1,-1,-1):
    no_plus_height = no[i]+A[i]
    try:
        total += no_minus_height[no_plus_height]
    except:
        pass
    
    try:
        no_minus_height[no[i]-A[i]] += 1
    except:
        no_minus_height[no[i]-A[i]] = 1
print(total)

Submission status: Accepted

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

N = int(readline())
A = list(map(int, readline().split()))
C = Counter()
ans = 0
for i in range(1, N+1):
    a = A[i-1]
    ans += C[i-a]
    C[a+i] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Api = [ai + i for i, ai in enumerate(A)]
jmA = [j - aj for j, aj in enumerate(A)]
count_Api = Counter(Api)
count_jmA = Counter(jmA)
ans = 0
for api, count in count_Api.items():
    ans += count * count_jmA[api]
print(ans)

Submission status: Accepted

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


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

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))


# ----------

N = ii()
A = lmii()

bd = defaultdict(int)
ac = defaultdict(int)
for i in range(N):
    a = b = i + 1
    c = d = A[i]
    bd[b-d] += 1
    ac[a+c] += 1

ans = 0
for k, v in bd.items():
    ans += v * ac[k]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = []
b = []
ans = 0
for i in range(N):
    a.append(i+1+A[i])
    b.append(i+1-A[i])
b = Counter(b)
for i in a:
    ans += b[i]
print(ans)

Submission status: Accepted

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

ap, am = [], []
for i in range(n):
    ap.append(i + 1 + a[i])
    am.append(i + 1 - a[i])

from collections import Counter
dicp = Counter(ap)
dicm = Counter(am)

ans = 0
for i, j in dicp.items():
    if i in dicm:
        ans += j * dicm[i]
print(ans)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from collections import defaultdict

N = int(input())
A =        list( map(int, input().split()) )	# 1 2 3 4 5 ...

B = []
D = defaultdict(lambda: 0)

for i in range(N):
	B.append([i,A[i]])
	
	k = i - A[i]
	D[k] += 1

ans=0
for i in range(N):
	k = i + A[i]
	ans += D[k]


print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


def main():
    N = int(input())
    A = [int(c) for c in input().split()]

    # 自分が1だったときのそれ以降
    lists = [0] * (N + 1)
    for i, a in enumerate(A):
        if i <= a:
            continue
        lists[i + 1 - a] += 1
    
    num = 0
    for i, a in enumerate(A):
        idx = i + 1
        if idx + a <= N:
            num += lists[idx + a]
    print(num)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
dif = []
for i in range(N):
    dif.append((i+1)-A[i])
#dif.sort()
counter = Counter(dif)

ans = 0
for i in range(N):
    ans += counter[(i+1)+A[i]]

print(ans)

Submission status: Accepted

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

import collections
n = int(input())
a = lmp()
plus = []
minus = []
for i in range(n):
    plus.append(i+1+a[i])
for i in range(n):
    minus.append(i+1-a[i])
p = list(collections.Counter(plus).items())
m = collections.Counter(minus)
# print(p)
# print(m)
ans = 0
for i in range(len(p)):
    tar = p[i][0]
    num = p[i][1]
    if tar in m:
        ans += num * m[tar]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
y = []
z =[]
for i in range(len(x)):
    y.append(x[i]+i)
    z.append(i-x[i])
count = 0 
dic = {}
for i in range(len(z)):
    if z[i] in dic :
        dic[z[i]]+= 1
    else :
        dic[z[i]] = 1
for i in range(len(y)) :
    dic[z[i]]-= 1 
    if y[i] in dic :
        count += dic[y[i]]
print(count)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product
import sys
import math
import numpy as np
import bisect

sys.setrecursionlimit(200000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def argsort(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)

def solve(N, A):
    # x: i-A[i]の列
    X = np.array([i-A[i] for i in range(N)], dtype=np.int)
    # y: i+A[i]の列
    Y = np.array([i+A[i] for i in range(N)], dtype=np.int)
    keys = np.argsort(X)
    X = X[keys]  # x[i] <= x[i+1]
    Y = Y[keys]
    ans = 0
    for y in Y:
        l = bisect.bisect_left(X, y)
        r = bisect.bisect_left(X, y+1)
        ans += r - l
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    print("{}".format(outputs))

Submission status: Accepted

Solution code:
import collections

def solve(k, r):
    count = {}
    ans = 0
    for i, n in enumerate(r):
        target = i-n
        ans += count.get(target, 0)
        count[i+n] = count.get(i+n, 0)+1
    return ans
k = int(input())
r = list(map(int, input().split()))
print(solve(k, r))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

score = {}

for i, a in enumerate(A):
  if i ==0:
    continue
  
  s = i-a
  if s not in score:
    score[s] = 0
  score[s]+=1

from bisect import bisect_left
ans = 0
for i, a in enumerate(A):
  if i+a in score:
    ans += score[i+a]
print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int,input().split()))

l = [0 for _ in range(n)]

for i in range(n):
	l[i] = a[i]-i-1

count = collections.Counter(l)
#print(l)
#print(count)
ans = 0
for i in range(n):
	ans += count[-i-1-a[i]]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    b[i]= i-a[0]-a[i]
d = defaultdict(int)
for i in range(1,n):
    d[b[i]] += 1
ans = 0
x = 0
for i in range(n-1):
    ans+=d[x]
    d[b[i+1]]-=1
    x -= -1+(a[i]-a[i+1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [0]*N
count = dict()
for i in range(1,N):
    B[i] = i-A[i]
    if B[i] in count:
        count[B[i]] += 1
    else:
        count[B[i]] = 1
total = 0
for i in range(N):
    if A[i]+i in count:
        total += count[A[i]+i]
    if i!= 0:
        count[B[i]] -= 1
print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 21:27:48 2020
"""

import sys
import numpy as np
import itertools

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
A = list(map(int,input().split()))

A = np.array(A)
B = np.arange(N)

x = A - B
y = A + B

x.sort()
y.sort()

ans = 0
i, j = 0, N - 1
#pre = 10**10
x1, y1 = 0, 0
while i < N and j >= 0:
    if -x[i] < y[j]:
        j -= 1
    elif -x[i] > y[j]:
        i += 1
    else:
        x1,y1 = 1, 1
        pre = y[j]
        while pre == -x[i+1]:
            x1 += 1
            i += 1
#            print('x',pre,x1)
        while pre == y[j-1]:
            y1 += 1
            j -= 1
#            print('y',pre,y1)
        i += 1
        j -= 1
        ans += x1 * y1
#        print()
#    print(i,j,x[i],y[j],x1,y1,ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
Hik=[0]*N
A=list(map(int,input().split()))
B=0
for i in range(N):
 Hik[max(-A[i]+N-1-i,0)]+=1
for j in range(N):
 if 0<=A[N-1-j]+j and A[N-1-j]+j<=N-1:
  B+=Hik[A[N-1-j]+j]
 Hik[max(-A[N-1-j]+j,0)]+=1
print(B)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
an=0;d={}
for i in range(n):
  d[l[i]+i]=d.get(l[i]+i,0)+1
  an+=d.get(i-l[i],0)
print(an)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N = int(input())
    A = inpl()
    Api = [a + i + 1 for i, a in enumerate(A)]
    Ami = [i + 1 - a for i, a in enumerate(A)]
    Api.sort()
    Ami.sort()
    # print(Api)
    # print(Ami)
    ans = 0
    for a in Api:
        ans += bisect_right(Ami, a) - bisect_left(Ami, a)
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

plus = defaultdict(int)

for i in range(n):
    plus[i+a[i]] += 1

pair = 0
for j in range(n):
    pair += plus[j-a[j]]

print(pair)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
t=dict()
for i in range(N):
    if A[i]-i in t:
        ans+=t[A[i]-i]
    t.setdefault(-A[i]-i,0)
    t[-A[i]-i]+=1
print(ans)

Submission status: Accepted

Solution code:
n =  int(input())
a = list(map(int,input().split()))
a_after = [a[i] - i for i in range(n)]
from collections import Counter
cnt = Counter()
for v in a_after:
    cnt[v] += 1
ret = 0  
for i in range(n):
    v = a[i] - i
    cnt[v] -= 1
    ret += cnt[-v-2*i]

print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
s = 0
for i in range(N):
    s += d[i-A[i]]
    d[A[i]+i] += 1
print(s)

Submission status: Accepted

Solution code:
n = int(input())

As = list(map(int, input().split()))

A_minus = []
minus_A_minus = []

for i in range(n):
    A_minus.append(As[i] - i - 1)
    minus_A_minus.append(-As[i] - i - 1)

dic_AM = {}
dic_MAM = {}

for i in range(n):
    AM = A_minus[i]
    MAM = minus_A_minus[i]
    if dic_AM.get(AM, None) is None:
        dic_AM[AM] = 1
    else:
        dic_AM[AM] += 1
    if dic_MAM.get(MAM, None) is None:
        dic_MAM[MAM] = 1
    else:
        dic_MAM[MAM] += 1

ans = 0

for k in dic_AM:
    if k in dic_MAM:
        ans += dic_AM[k] * dic_MAM[k]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
X = defaultdict(int)
Y = defaultdict(int)
for i in range(N):
    x = A[i] + i
    y = A[i] - i
    X[x] += 1
    if y < 0:
        Y[y] += 1
ans = 0
for y, k in Y.items():
    ans += k * X[-y]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, A = int(input()), list(map(int, input().split()))
temp = [0] * N
for i in range(1, N+1):
    temp[i-1] = i + A[i-1]
temp = Counter(temp)
result = 0
for j in range(1, N+1):
    s = temp.get(j - A[j-1])
    if s != None:
        result += s
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))

    A_ex = [(i, a) for i, a in enumerate(A)]

    # i < jを仮定する
    counter = Counter()
    cnt = 0
    for i, a in A_ex[::-1]:
        cnt += counter[i+A[i]]
        counter[i-A[i]] += 1
    print(cnt)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split(' ')]

left = [0] * N
right = [0] * N

for i, a in enumerate(A):
  if i - a >=0:
    right[i-a] += 1
  if i + a < N:
    left[i + a] += 1
#print(right)
#print(left)
ans = 0
for l, r in zip(left, right):
  ans += l*r
print(ans)

Submission status: Accepted

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

a = tuple(a[i]+i for i in range(n))

d = {}
ret = 0
for i in range(n):
    q = i*2 - a[i]
    if q in d:
        ret = ret + d[q]
    if a[i] in d:
        d[a[i]] = d[a[i]] + 1
    else:
        d[a[i]] = 1

print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

memo = defaultdict(int)
answer = 0
for i, x in enumerate(A, 1):
    answer += memo[i - x]
    memo[x + i] += 1

print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
wa={}
sa={}
i=1
for x in a:
    w=x+i
    s=i-x
    if w in wa:
        wa[w]+=1
    else:
        wa[w]=1
    if s in sa:
        sa[s]+=1
    else:
        sa[s]=1
    i+=1
ans=0
for k,v in wa.items():
    if k in sa:
        ans+=sa[k]*v
#print(wa)
#print(sa)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dict = {}
tcnt = 0
for i in range(n):
    j = i + 1
    if (j - a[i]) in dict:
        tcnt += dict[j - a[i]]
    if (a[i] + j) in dict:
        dict[a[i] + j] += 1
    else:
        dict[a[i] + j] = 1
print(tcnt)

Submission status: Accepted

Solution code:
from _collections import defaultdict
n=int(input())
A=list(map(int,input().split()))

X=[A[i]-(i+1) for i in range(n)]
Y=[-A[i]-(i+1) for i in range(n)]
ans=0

P=defaultdict(int)
Q=defaultdict(int)

for x in X:
    P[x]+=1
for y in Y:
    Q[y]+=1

p=set(P.keys())
q=set(Q.keys())

r=p&q

for key in r:
    ans+=P[key]*Q[key]
print(ans)

Submission status: Accepted

Solution code:

def task(n, a):
    total = 0
    tl = [0] * n
    tr = [0] * n

    for i in range(0, n):
        l = i - a[i]
        r = i + a[i]

        if l >= 0:
            tl[l] += 1

        if r < n:
            tr[r] += 1

    for i in range(0, n):
        if tl[i] > 0 and tr[i] > 0:
            total += tl[i] * tr[i]

    print(total)


n = int(input())
a = list(map(int, input().split()))

task(n, a)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans = 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)