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

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


cnt_height_plus_ind = {}
cnt_ind_minus_height = {}

for ind in range(N):
    height = heights[ind]

    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

ans = 0
for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val] * cnt_ind_minus_height[val]

print(ans)

Submission status: Accepted

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

N = int(input())

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


cnt_height_plus_ind = {}
cnt_height_minus_ind = {}
cnt_ind_minus_height = {}
cnt_minus_height_minus_ind = {}

for ind in range(N):
    height = heights[ind]

    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

    if height - ind not in cnt_height_minus_ind:
        cnt_height_minus_ind[height - ind] = 0
    cnt_height_minus_ind[height - ind] += 1

    if - ind - height not in cnt_minus_height_minus_ind:
        cnt_minus_height_minus_ind[-ind-height] = 0
    cnt_minus_height_minus_ind[-ind-height] += 1
    

ans = 0
#for val in cnt_height_minus_ind:
#    if val in cnt_minus_height_minus_ind:
#        ans += cnt_height_minus_ind[val] * cnt_minus_height_minus_ind[val]

for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val] * cnt_ind_minus_height[val]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
n = int(input())
aa = np.array(list(map(int, input().split())))
cnt = 0
pl = aa + np.array(range(n))
ms = -aa + np.array(range(n))
common = set(pl).intersection(set(ms))

dic_pl = Counter(pl)
dic_ms = Counter(ms)

for k in dic_ms.keys():
    cnt += dic_ms[k] * dic_pl.get(k,0)
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[0]*n
    c=[0]*n
    ans=0
    for i in range(n):
        b[i]=a[i]+i
    for i in range(n):
        c[i]=i-a[i]
    bc=set(b).intersection(set(c))
    bd={}
    cd={}
    for i in bc:
        bd[i]=0
    for j in b:
            if j in bc:
                bd[j]+=1
    for i in bc:
        cd[i]=0
    for j in c:
            if j in bc:
                cd[j]+=1
    ansb=list(bd.values())
    ansc=list(cd.values())
    for k in range(len(bc)):
        ans+=ansb[k]*ansc[k]
    print(ans)
resolve()

Submission status: Accepted

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

N = int(input())

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


cnt_height_plus_ind = {}
cnt_height_minus_ind = {}
cnt_ind_minus_height = {}
cnt_minus_height_minus_ind = {}

for ind in range(N):
    height = heights[ind]

    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

    if height - ind not in cnt_height_minus_ind:
        cnt_height_minus_ind[height - ind] = 0
    cnt_height_minus_ind[height - ind] += 1

    if - ind - height not in cnt_minus_height_minus_ind:
        cnt_minus_height_minus_ind[-ind-height] = 0
    cnt_minus_height_minus_ind[-ind-height] += 1
    

ans = 0
for val in cnt_height_minus_ind:
    if val in cnt_minus_height_minus_ind:
        ans += cnt_height_minus_ind[val] * cnt_minus_height_minus_ind[val]

for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val] * cnt_ind_minus_height[val]

print(ans//2)

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loop(N,A):
    L = np.array([0 for i in range(N+1)])
    R = np.array([0 for i in range(N+1)])

    for i in range(N):
        temp = A[i]
        if i+1+temp <= N:
            L[i+1+temp] += 1
        if i+1-temp >= 0:
            R[i+1-temp] += 1

    return np.sum(L*R)

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

    res = loop(N,A)

    print(res)




main()

Submission status: Accepted

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

ans = 0
dic = {}
for i in range(N):
    ans += dic.get(i - A[i], 0)
    dic[i + A[i]] = dic.get(i + A[i], 0) + 1
    # for j in range(i+1, N):
    #     if i - A[i] == j + A[j]:
    #     # if i - j == A[i] + A[j]:
    #         ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
dic = {}
dic[1 + A[0]] = 1
for i in range(2, N+1):
    if i - A[i-1] in dic:
        ans += dic[i - A[i-1]]
    if i + A[i-1] in dic:
        dic[i + A[i-1]] = dic[i + A[i-1]] + 1
    else:
        dic[i + A[i-1]] = 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


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

# j - A[j]
hiku = []
# i + A[i]
tasu = []

for i, a in enumerate(A, 1):
    hiku.append(i - a)
    tasu.append(i + a)

hiku_c = collections.Counter(hiku)
tasu_c = collections.Counter(tasu)

ans = 0
for key, value in tasu_c.items():
    if key in hiku_c.keys():
        ans += value * hiku_c[key]

print(ans)

Submission status: Accepted

Solution code:
#解説を見て実装
from collections import Counter

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめL_t = defaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    L_t = Counter(L)
    R_t = Counter(R)
    cnt = 0
    x_candidate = set(L) & set(R)
    for x in x_candidate:
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        cnt += l_candidate * r_candidate

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    INF = 10 ** 9

    L = np.array([0 for i in range(N+1)])
    R = np.array([0 for i in range(N+1)])

    for i in range(N):
        temp = A[i]
        if i+1+temp <= N:
            L[i+1+temp] += 1
        if i+1-temp >= 0:
            R[i+1-temp] += 1

    res = np.sum(L*R)

    print(res)




main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
cnt1 = defaultdict(int)
cnt2 = defaultdict(int)
for i in range(N):
    cnt1[A[i] + i + 1] += 1
    cnt2[i + 1 - A[i]] += 1
ans = 0
for k, v in cnt1.items():
    ans += v * cnt2[k]
print(ans)

Submission status: Accepted

Solution code:
# 解答みた
N=int(input())
A=[int(x) for x in input().split()]
X={}
Y={}
for i in range(N):
  L=i+A[i]
  R=i-A[i]
  X[L]=X[L]+1 if L in X else 1
  Y[R]=Y[R]+1 if R in Y else 1
ans=0
for n in X:
  if n in Y:
    ans+=X[n]*Y[n]
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


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

left = []
right = []

for i, a in enumerate(A, 1):
    left.append(i - a)
    right.append(i + a)

left_counter = collections.Counter(left)
right_counter = collections.Counter(right)

ans = 0
for i, j in right_counter.items():
    if i in left_counter:
        ans += j * left_counter[i]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dic={}
ans=0
d=input().split(" ")
for i in range(0,len(d)):
    k=int(d[i])
    if i-k in dic:
        ans+=dic[i-k]
    if i+k in dic:
        dic[i+k]+=1
    else:
        dic[i+k]=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = [int(v) for v in input().split()]

ans = 0
dic = defaultdict(int)

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

for i,a in enumerate(A):
    ans += dic[a+i]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
data1 = [0 for _ in range(n)]
data2 = [0 for _ in range(n)]
for i,x in enumerate(a):
    if i+x <= n-1:
        data1[i+x] += 1
    if i-x >= 0:
        data2[i-x] += 1

ans = 0
for i in range(n):
    ans += data1[i]*data2[i]
print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n=int(input())
#n=10**5
a=list(map(int,input().split()))
#a=[0 if i%2==0 else 1 for i in range(n)]
l=defaultdict(int)
r=defaultdict(int)
for i in range(n):
    ii=i+1
    l[ii+a[i]]+=1
    r[(ii-a[i])]+=1
#print(l)
#print(r)
ans=0
for each in l.keys():
    if each in r.keys():
        ans+=l[each]*r[each]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
src=list(map(int,input().split()))
ans=0
d=defaultdict(int)
e=[]
for i,s in enumerate(src,1):
  l=i+s
  r=i-s
  d[l]+=1
  ans+=d[r]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# import itertools
import collections


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    # # TLE
    # c = itertools.combinations_with_replacement(range(1, N + 1), 2)
    # cnt = 0
    # for i in c:
    #     x = i[0]
    #     y = i[1]
    #     if x + A[x - 1] == y - A[y - 1]:
    #         cnt += 1
    # print(cnt)

    L = []  # 左辺
    R = []  # 右辺
    for i in range(N):
        x = y = i + 1
        L.append(x + A[i])
        R.append(y - A[i])
    cl = collections.Counter(L)
    cr = collections.Counter(R)
    ans = 0
    for i in range(N):
        if i in cl and i in cr:
            ans += cl[i] * cr[i]
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import *
n=int(input())
a=[int(x) for x in input().split()]

f=[]
for i in range(n):
	f.append(0)
for i in range(n):
	if a[i]<n and (i+1)>a[i]:
		f[(i+1)-a[i]]+=1

#print(f)
ans=0
for i in range(n):
	#print(a[i]+i+1)
	if a[i]+i+1<n:
		ans+=f[a[i]+(i+1)]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

d = {}
for i, ai in enumerate(a):
    l = ai + i+1
    if l in d:
        d[l] += 1
    else:
        d[l] = 1

p = 0
for i, ai in enumerate(a):
    r = i+1 - ai
    p += d.get(r, 0)

print(p)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
l = [0]*n
r = [0]*n
for i in range(n):
    l[i] = i+a[i]
    r[i] = i-a[i]
    
l=Counter(l)
r=Counter(r)
ans = 0
for i in range(max(r.keys())+1):
    ans += l[i]*r[i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = 0
ia = []
ja = []
dia={}
dja={}
for i in range(n):
  dia[i+a[i]] = dia.get(i+a[i],0)+1
  dja[i-a[i]] = dja.get(i-a[i],0)+1
ans = 0
for di,nmi in dia.items():
  nmj = dja.get(di,0)
  ans += nmi*nmj

print(ans)

Submission status: Accepted

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

A1, A2 = {}, {}
for i, a in enumerate(A):
    key1 = str(-a-i)
    if key1 in A1:
        A1[key1] = (key1 in A1) * A1[key1] + 1
    else:
        A1[key1] = 1
    key2 = str(a-i)
    if key2 in A2:
        A2[key2] += 1
    else:
        A2[key2] = 1

cnt = 0
for key, value in A1.items():
    if key in A2:
        cnt += value * A2[key]

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

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

iA = [i+n for i, n in enumerate(A)]
jA = [i-n for i, n in enumerate(A)]
dict1 = Counter(iA)
dict2 = Counter(jA)

ans = 0
for key, value in dict1.items():
    ans += value * dict2[key]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict

setrecursionlimit(10 ** 9)


def input():
    return stdin.readline().strip()


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

d = defaultdict(int)
for i, a in enumerate(A, 1):
    d[i + a] += 1

ans = 0
for i, a in enumerate(A, 1):
    ans += d[i - a]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    m = {}
    for i in range(N):
        x = i - A[i]
        if m.get(x) == None:
            m[x] = [1, 0]
        else:
            m[x][0] += 1
    for i in range(N):
        y = i + A[i]
        if m.get(y) != None:
            m[y][1] += m[y][0]
    ans = 0
    for key in m:
        ans += m[key][1]
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
c = Counter()
ans = 0
for i, x in enumerate(int(x) for x in input().split()):
    ans += c[i - x]
    c[i + x] += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
L = [0] * N
R = list()
for i in range(N):
  R.append(i-A[i])
  if(i+A[i]<=N-1):
    L[i+A[i]] += 1
for r in R:
  if(r > 0):
    ans += L[r]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=map(int,input().split())  
b,c=[],[]
for i,q in enumerate(a):
  b.append(i+q)
  c.append(i-q)
from collections import*
b=Counter(b).items()
c=Counter(c)
z=0
for d,e in b:z+=e*c[d]
print(z)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
C = sorted([-A[i] - i for i in range(n)])
from bisect import *
print(sum(bisect(C, b) - bisect_left(C, b) for b in [A[i] - i for i in range(n)]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [i+a[i] for i in range(n)]
r = [j-a[j] for j in range(n)]
import collections
cl = collections.Counter(l)
cr = collections.Counter(r)
ans = 0
for i in cl.keys():
    if i in cr.keys():
        ans += cl[i]*cr[i]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))

l = {}
r = {}

for i in range(n):
    x = i + an[i]
    if x not in l:
        l[x] = [i]
    else:
        l[x].append(i)

    x = i - an[i]
    if x not in r:
        r[x] = [i]
    else:
        r[x].append(i)

sum = 0
for k in l:
    if k in r:
        sum += len(l[k])*len(r[k])

print(sum)

Submission status: Accepted

Solution code:
N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*N
maxi=max(a)
for i in range(N):
  s.append(i-a[i])
  if i+a[i]<N:
    num[i+a[i]]+=1
for i in range(N):
  if s[i]>=0:
    count+=num[s[i]]
print(count)

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)

Submission status: Accepted

Solution code:
N=int(input())
count=0
a=list(map(int,input().split()))
w=[]
s=[]
num=[0]*N
maxi=max(a)
for i in range(N):
  s.append(1+i-a[i])
  if 1+i+a[i]<N:
    num[1+i+a[i]]+=1
for i in range(N):
  if s[i]>=0:
    count+=num[s[i]]
print(count)

Submission status: Accepted

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

xdic={}
ydic={}

for i,a in enumerate(alist):
    #xlist.append((i+1)+a)
    #ylist.append((i+1)-a)
    tmpx=(i+1)+a
    tmpy=(i+1)-a
    if tmpx in xdic:
        xdic[tmpx]=xdic[tmpx]+1
    else:
        xdic[tmpx]=1
    if tmpy > 0:
        if tmpy in ydic:
            ydic[tmpy]=ydic[tmpy]+1
        else:
            ydic[tmpy]=1

output=0
for y in ydic:
    if y in xdic:
        output+= xdic[y]*ydic[y]

print(output)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
ar = defaultdict(list)
al = defaultdict(list)

for i in range(n):
    al[i+a[i]].append(i)
    ar[i-a[i]].append(i)

x = al.keys()

ans = 0
for i in x:
    ans += len(ar[i]) * len(al[i])

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
x = dict()
ans = 0

for i in range(n):
    tmp = i + A[i]
    if tmp not in x:
        x[tmp] = 1
    else:
        x[tmp] += 1

for j in range(n):
    l = j - A[j]
    if l in x:
        ans += x[l]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
L = [i+x for i, x in enumerate(A)]
R = [i-x for i, x in enumerate(A) if i-x > 0]

from collections import Counter
P = Counter(L)
Q = Counter(R)
 
ans = 0
for k, v in P.items():
  if k in Q:
    ans += v*Q[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
cnt_i = defaultdict(lambda :0)
cnt_j = defaultdict(lambda :0)
for i in range(n):
    temp_i = a[i] + i + 1
    temp_j = i + 1 - a[i]
    cnt_i[temp_i] += 1
    cnt_j[temp_j] += 1

ans = sum(v * cnt_j[i] for i,v in cnt_i.items())
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
d_1 = Counter()
d_2 = Counter()
A = map(int, input().split())
for i, a in enumerate(A):
    i += 1
    d_1[i - a] += 1
    d_2[i + a] += 1

c = 0
for k, v in d_1.items():
    if d_2[k] > 0:
        c += v * d_2[k]
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect

n = int(input())
a = list(map(int, input().split()))
# b = a -1 とすると、bi+bj = -2*i or -2+j となるi,jを見つける
# sortして2分探索すると解ける
b = [a[i] - (1 + i) for i in range(0, n)]
b, idx = zip(*sorted(zip(b, range(1, n + 1))))
# print(b)
ans = 0
for i in range(n):
    # b[i]を固定して二分探索
    r = bisect.bisect_right(b, -b[i] - 2 * idx[i])
    l = bisect.bisect_left(b, -b[i] - 2 * idx[i])
    ans += r - l
    # if r - l != 0:
    # print(i, r, l, -b[i] - 2 * idx[i])
print(ans)

Submission status: Accepted

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


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    ret = 0
    X = defaultdict(int)
    for i, a in enumerate(A):
        X[a+i] += 1

        if 0 <= i-a:
            ret += X[i-a]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

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

plus = []
minus = []

for i, j in enumerate(A):
    # print(i, j)
    plus.append(i+j)
    minus.append(i-j)

# print(plus)
# print(minus)

plus_count = Counter(plus)
minus_count = Counter(minus)
# print(plus_count)
# print(minus_count)


for i,j in plus_count.items():
    # print(i, j)
    if i in minus_count:
        ans += j * minus_count[i]
        # print(i, j)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

a = list(map(int,input().split()))
ans = 0
cc = Counter()

for i,val in enumerate(a):
    if i - val > 0:
        ans+=cc[i-val]
    cc[i+val]+=1

print(ans)

Submission status: Accepted

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

agents = {}
n_pair = 0

for i, a in enumerate(a_list):
  x = i - a
  if x not in agents:
    agents[x] = 0
  agents[x] += 1

for i, a in enumerate(a_list):
  x = i + a
  if x in agents:
    n_pair += agents[x]
print(n_pair)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
d={}
e={}
c=0

for i in range(n):
    if a[i]+i not in d:
        d[a[i]+i]=1
    else:
        d[a[i]+i]+=1
    if i-a[i] not in e:
        e[i-a[i]]=1
    else:
        e[i-a[i]]+=1
for i in d.keys():
    if i not in e:
        continue
    else:
        c+=d[i]*e[i]  

print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
n = int(input())
a = [int(i) for i in input().split()] 

"""#TLE
ans = 0
for i in range(n):
    for j in range(i+1, n):
        #print(i, j)
        if j - i == a[i] + a[j]:
            ans += 1
print(ans)
"""

"""#DP
A = [[a[i], i+1] for i in range(n)]
#print(A)
A.sort()
#print(A)
dp = [0 for _ in range(n)]
dp[0] = 0
if abs(A[0][1] - A[1][1]) == A[0][0] + A[1][0]:
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2, n):
    dp[i] = 
"""

#解説AC
ans = 0
A = [[i+1, a[i]] for i in range(n)]
#print(A)
L = [0 for i in range(n)]
R = [0 for i in range(n)]
for i in range(n):
    L[i] = A[i][0] + A[i][1] 
    R[i] = A[i][0] - A[i][1]
#print(L)
#print(R)
cl = collections.Counter(L)
cr = collections.Counter(R)
#print(cl)
#print(cr)
for i in set(L):
    ans += cl[i] * cr[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        cnt += buf1 * buf2
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
h = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i + h[i])
    b.append(i - h[i])

x = Counter(a)
y = Counter(b)

z = set(a)
ans = 0
for i in z:
    ans += x[i] * y[i]

print(ans)

Submission status: Accepted

Solution code:
def e_this_message_will_self_destruct_in_5s():
    N = int(input())
    A = [int(i) for i in input().split()]

    add = [j + a for j, a in enumerate(A, 1)]
    diff = sorted([k - a for k, a in enumerate(A, 1)])

    from bisect import bisect_left as bleft
    return sum([bleft(diff, p + 1) - bleft(diff, p) for p in add])

print(e_this_message_will_self_destruct_in_5s())

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)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, *A = map(int, open(0).read().split())
ans, d = 0, defaultdict(int)
for i, a in enumerate(A, 1):
    x, y = i+a, i-a
    d[x] += 1
    ans += d[y]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
ans=0
L={}
R={}
for i in range(N):
    if a[i]+i in L:
         k=L.get(a[i]+i)
         del L[a[i]+i]
         L[a[i]+i]=k+1
    else:
        L[a[i]+i]=1
    if i-a[i]>0:
        if i-a[i] in R:
             k=R.get(i-a[i])
             del R[i-a[i]]
             R[i-a[i]]=k+1
        else:
            R[i-a[i]]=1
for x in L.keys():
    if x in R:
        ans+=L.get(x)*R.get(x)
print(ans)

Submission status: Accepted

Solution code:
import collections
N=int(input())
n_list=input().split()
count=0
L_list=[]
R_list=[]
for i,item in enumerate(n_list) :
  L_list.append(str(i+int(item)))
  R_list.append(str(i-int(item)))
L_dic=collections.Counter(L_list)
R_dic=collections.Counter(R_list)
count=0
for i in range(N) :
  L_count=L_dic[str(i)]
  R_count=R_dic[str(i)]
  count+=L_count*R_count
print(count)

Submission status: Accepted

Solution code:

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

    # j-i == Ai + Aj -> i+Ai == j-Aj
    # L: i+Ai, R: i-Ai

    dic = {}
    ans = 0
    for i in range(N):
        L = i + A[i]
        R = i - A[i]
        if L not in dic:
            dic[L] = 1
        else:
            dic[L] += 1
        if R in dic:
            ans += dic[R]
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def e_this_message_will_self_destruct_in_5s():
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]

    add = [j + a for j, a in enumerate(A, 1)]
    diff = [k - a for k, a in enumerate(A, 1)]
    count = Counter(diff)
    return sum([count[p] for p in add])

print(e_this_message_will_self_destruct_in_5s())

Submission status: Accepted

Solution code:
n=int(input())
heights=list(map(int,input().split(" ")))
dic={}
res=0
for i in range(n):
    if heights[i]-i not in dic:
        dic[heights[i]-i]=1
    else:
        dic[heights[i]-i]+=1
for j in range(n):
    if -heights[j]-j in dic:
        res+=dic[-heights[j]-j]
print(res)

Submission status: Accepted

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

l = [0]*n
r = [0]*n

l = [i+a[i] for i in range(n)]
r = [i-a[i] for i in range(n)]
ld = {}
rd = {}

c = 0

for i in range(n):
	if l[i] in ld:
		ld[l[i]] += 1
	else:
		ld[l[i]] = 1
	if r[i] in rd:
		rd[r[i]] += 1
	else:
		rd[r[i]] = 1

for i in ld.keys():
	if i in rd:
		c += ld[i]*rd[i]	
	
print(c)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

dic = {}
point = 0

for i,j in enumerate(a):
    if i+j in dic:
        dic[i+j] += 1
    else:
        dic[i+j] = 1

for i,j in enumerate(a):
    if i-j in dic:
        point += dic[i-j]

print(point)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    H = LI()
    ans = 0
    cnt_plus_height_plus_idx = defaultdict(int)
    cnt_minus_height_plus_idx = defaultdict(int)

    for idx in range(N):
        cnt_plus_height_plus_idx[H[idx] + idx] += 1
        cnt_minus_height_plus_idx[- H[idx] + idx] += 1

    ans = 0

    for k, v in cnt_plus_height_plus_idx.items():
        if k in cnt_minus_height_plus_idx:
            ans += v * cnt_minus_height_plus_idx[k]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    base = [0] * N
    for i, a in enumerate(A):
        if i - a >= 0: base[i-a] += 1
    count = 0
    for i, a in enumerate(A):
        if i + a < N: count += base[i + a]
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, *A = map(int, open(0).read().split())
ans, d = 0, {}
for i, a in enumerate(A, 1):
    x, y = i+a, i-a
    d[x] = d.get(x, 0)+1
    ans += d.get(y, 0)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

L = []
R = []

for i in range(N):
    L.append(i+1 + A[i])
    R.append(i+1 - A[i])

L.sort()
R.sort()

#print(L)
#print(R)

temp = 0
ans = 0
j = 0
for i in range(N):
    if i >= 1 and L[i] == L[i-1]:
        ans += temp
        continue
    temp = 0
    while j < N and L[i] >= R[j]:
        if L[i] == R[j]:
            temp += 1
        j += 1
    ans += temp

print(ans)