Problem:


Score : 400 points

Problem Statement

Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.

He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:

a < b + c

b < c + a

c < a + b

How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

Constraints

All values in input are integers.

3 \leq N \leq 2 \times 10^3

1 \leq L_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N
L_1 L_2 ... L_N

Constraints

Print the number of different triangles that can be formed.

Sample Input 1

4
3 4 2 1

Sample Output 1

1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.

Sample Input 2

3
1 1000 1

Sample Output 2

0

No triangles can be formed.

Sample Input 3

7
218 786 704 233 645 728 389

Sample Output 3

23



Sample input:
4
3 4 2 1


Sample output:
1

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, *L= map(int, open(0).read().split())
X = sorted(L)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ub = bisect_left(X, X[i] + X[j])
        ans += ub - (j + 1)
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0
while len(L) >= 3:
    tmp = L.pop(0)
    left = 0
    right = len(L) - 1
    while left < right:
        if L[left] + L[right] > tmp:
            ans += right - left
            left += 1
        else:
            right -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

N=input()
L=map(int, sys.stdin.readline().split())
L.sort()

ans=0
for i in range(N):
    for j in range(i+1,N):
        a=L[i]
        b=L[j]
        max_c=a+b
        min_c=max(a-b,b-a)
        p_max_c=bisect_left(L,max_c)
        p_min_c=max(bisect_right(L,min_c),j)
        ans+=p_max_c-p_min_c-1

print ans

Submission status: Accepted

Solution code:
def triangles(a): 
    n = len(a) 
    a.sort() 
    count = 0
    for i in range(0,n-2):
        k = i + 2
        for j in range(i+1,n): 
            while (k < n and a[i] + a[j] > a[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
    return count
n=int(input())
a=list(map(int,input().split()))
print(triangles(a))

Submission status: Accepted

Solution code:
import bisect

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        ind = bisect.bisect_left(nums, nums[a] + nums[b])
        ans += ind - 1 - b
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from itertools import accumulate
def main():
    N = int( input())
    L = list( map( int, input().split()))
    d = defaultdict( int)
    ans = 0
    
    for l in L:
        d[l] += 1
    L.sort()
    R = list( set(L))
    R.sort()
    for e in d:
        if d[e] >= 3:
            ans += d[e]*(d[e]-1)*(d[e]-2)//6
        if d[e] >= 2:
            cnt = 0
            t = d[e]*(d[e]-1)//2
            for l in R:
                if l == e:
                    continue
                if l < 2*e:
                    cnt += t*d[l]

            ans += cnt
    T = [0]*(10**4)
    M = len(R)
    Z = [0]*(10**4)

    for i in range(M):
        for j in range(i+1, M):
            e = R[i]
            f = R[j]
            t = d[e]*d[f]
            T[ abs(e-f)+1] += t
            T[ e+f] -= t
            if abs(e-f) < e:
                Z[e] += t
            if abs(e-f) < f:
                Z[f] += t
    S = list( accumulate(T))
    a = 0

    for e in d:
        if S[e] > 0:
            a += (S[e] - Z[e])*d[e]

    print(ans+a//3)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  n = int(raw_input())
  sticks = list(sorted(map(int, raw_input().split())))
  result = 0

  for x in xrange(n):
      z = x + 2
      for y in xrange(x+1, n):
          while (z < n and sticks[x] + sticks[y] > sticks[z]):
              z += 1
          result += z - y -1
  print(result)

main()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ancilla = [N] * 2001
    for i in range(2001):
        for j in range(N):
            if L[j] > i:
                ancilla[i] = j
                break

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            x = L[i] + L[j]
            tmp = ancilla[x-1] - (j+1)
            if tmp > 0:
                ans += tmp

    print(ans)

solve()

Submission status: Accepted

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

L.sort()
MAX = L[-1]
num = [0 for _ in range(MAX+1)]
index = 0
for l in L:
    if index == l:
        num[index] += 1
    else:
        num[l] += 1
        for i in range(index+1, l+1):
            num[i] += num[i-1]
        index = l

ans = 0
# print(num)
for i in range(N):
    for j in range(i+1, N):
        # print("{0} and {1}".format(L[i], L[j]))
        max_rest = min(MAX, L[i]+L[j]-1)
        # print(max_rest)
        # print(max(0, max_rest - j - 1))
        ans += max(0, num[max_rest] - j - 1)
print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())
L = sorted(list(map(int, input().split())))

col = collections.Counter(L)
cmemo = [0] * 1010
for x in list(col.keys()):
    cmemo[x] += col[x]
for i in range(1, 1010):
    cmemo[i] += cmemo[i-1]

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        a, b = L[i], L[j]
        cmin, cmax = b-a, min(a+b, 1009)
        if cmin < a:
            ans += cmemo[cmax-1] - cmemo[cmin] - 2
        else:
            ans += cmemo[cmax-1] - cmemo[cmin] - 1
print(ans//3)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
N = I()
ans = int(0)
L = LI()
L.sort()
Lmax = max(L)
Long = [0]*(Lmax+1)
for i in range(Lmax+1):
    k = int(0)
    while k<N and i+1>L[k] :
        Long[i] += 1
        k +=1

#sumL = [[0]*(Lmax+1) for _ in range(Lmax+1)]
#for i in range(Lmax+1):
#    for j in range(i+1,Lmax+1):
#        sumL[i][j] = sum(Long[i:(j+1)])

s = int(0)
t = int(0)
for i in range(N):
    for j in range(i+1,N):
#        s = abs(L[i] - L[j]) +1
        t = L[i] + L[j] -1
        count =int(0)
        count += max(Long[min(t,Lmax)]-j-1,0)
        ans += count

#        count += sumL[s][min(Lmax,t)]
#        if s<=L[i]<=t:
#            ans -=1
#        if s <= L[j] <= t:
#            ans -= 1
#        ans += max(count,0)
#        for k in range(j+1,N):
#            if s<=L[k]<=t:
#                ans +=1
#        print(s,t)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
def main():
    _ = int(input())
    l = list(map(int,input().split()))
    d = defaultdict(int)
    for i in l:
        d[i] += 1
    dk = sorted(list(d.keys()))
    dk2 = [i*2 for i in dk]
    ans = 0
    while dk:
        x = dk[-1]
        _ = dk2.pop(-1)
        bs = bisect.bisect(dk2,x)
        tmp = dk[bs:]
        if not tmp:
            break
        for i in tmp:
            for j in dk:
                if i+j > x and i >= j:
                    if i == j and i == x:
                        ans += d[x]*(d[x]-1)*(d[x]-2)//6
                    elif i == j:
                        ans += d[x]*d[i]*(d[i]-1)//2
                    elif i == x:
                        ans += d[x]*(d[x]-1)*d[j]//2
                    else:
                        ans += d[x]*d[i]*d[j]
        del dk[-1]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

count = 0

for a in range(n-2):
    k = a+2
    for j in range(a+1,n):
        while (k < n and arr[a] + arr[j] > arr[k]):
            k+=1
        
        if k>j:
            count += k-j-1
        
print(count)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
l = sorted(list(map(int, input().split())))

result = 0

for i in range(N):
  for j in range(i + 1, N):
    cur = bisect.bisect_left(l, l[i] + l[j]) - j - 1
    result += cur if cur > 0 else 0   

print(result)

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
L.sort()
c=0
for i in range(N-2):
  k=i+2
  for j in range(i+1,N-1):
    s=L[i]+L[j]
    c=c+k-j-1
    while L[k]<s and k<=N-2:
      k=k+1
      c=c+1
    if k==j+1 and s<=L[k]:
      k=k+1
    if k==N-1 and L[k]<s:
      c=c+1
print(c)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort(reverse=True)
ans = 0
P = []
for i in range(N-1):
    for j in range(i+1,N):
        P.append(L[i]+L[j])
P.sort()
now = 0
ans = 0
for i in range(N-2):
    now += N - (i + 1)
    index = bisect.bisect_left(P,L[i]+0.1)
    ans += (len(P) - index)-now
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

n=int(input())
listl = [int(i) for i in input().split()]

listl.sort()
#print(listl)

ans = 0

for i in range(n-1,1,-1):
    c = listl[i]
    for j in range(i-1,0,-1):
        b = listl[j]
        a = bisect_right(listl,c-b)
        #print(a)
        num = j-a
        #print("num",num)
        if num>0:
            ans+=num
        

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l_list = list(map(int, input().split()))
l_list.sort()

score = 0
#a_before = 0
#b_before = 0
for i in range(0, n - 2):
  a = l_list[i]
  #if a_before == a:
  #  continue
  #a_before = a
  
  for j in range(i + 1, n - 1):
    b = l_list[j]
    #if b_before == b:
    #  continue
    #b_before = b
    
    #minimum = b - a
    maximum = a + b
    
    #idx_minimum = bisect.bisect_right(l_list, minimum)
    idx_maximum = bisect.bisect_left(l_list, maximum)
    
    score += max(0, idx_maximum - j - 1)
        
print(score)

Submission status: Accepted

Solution code:
import bisect

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

L.sort()

cnt = 0
for x in range(N):
    for y in range(x+1, N):
        index = bisect.bisect_left(L, L[x]+L[y])
        if index - y - 1 >=0:
            cnt += (index - y - 1)

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l = list(reversed(sorted(l)))
ans = 0
for i in range(1,n):
    start = 0
    for j in range(i+1,n):
        l2 = l[i]+l[j]
        for k in range(start, i):
            if l[k] < l2:
                start = k
                ans += i - k
                break
print(ans)

Submission status: Accepted

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

li.sort()
#mod_li=[[i,num] for i,num in enumerate(li)]

result=0
for i in range(len(li)-2):
  tmp=i+2
  for j in range(i+1,len(li)-1):
    for k in range(tmp,len(li)):
      if li[i]+li[j]<=li[k]:
        tmp=k-1
        if tmp-j>0:
          result+=tmp-j
        break
      elif k==len(li)-1:
        tmp=k
        result+=tmp-j
        break
print(result)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
L=[int(i) for i in input().split()]
L.sort()
count=0
for i in range(N-2):
    a=0
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        if l<=L[j+1]:
            a=0
        elif l>L[N-1]:
            a=1
            break
        else:
            idx=bisect.bisect_left(L,l)
            count=count+(idx-j-1)
    if a==1:
        b=N-j-1
        B=(b+1)*b//2
        count=count+B
print(count)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
cnt=0
l= list(map(int, input().split()))
l.sort(reverse=True)
k=[[0 for i in range(n-2)] for j in range(n-2)]
for i in range(n-2):
    for j in range(i,n-2):
        k[i][j-i]=-l[i+1]-l[j+2]
#print(k)
for i in range(n-1):
    x=i
    while x<n-2:
        cnt+=bisect.bisect_left(k[x],-l[i])
        #print(l[i],bisect.bisect_left(k[x],-l[i]))
        x+=1
print(cnt)

Submission status: Accepted

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

N = int(input())
A = sorted(map(int, input().split()))
ans = 0
 
for i in range(0, N-2):
       for k in range(i+1, N-1):
            ans += bisect.bisect_left(A, A[i]+A[k])-k-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
List = [int(i) for i in input().split()]
List=sorted(List)
ans = 0
for i in range(0,n-1):
  for j in range(i+1,n):
    tmp1 = List[i]
    tmp2 = List[j]
    a=bisect.bisect_left(List,tmp1+tmp2)
    ans += a -j-1
print(ans)

Submission status: Accepted

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

llist.sort()
res = 0
for i in range(n-2):
    prev = n-1
    for j in range(n-2,i,-1):
        for k in range(prev, j, -1):
            if llist[k] < llist[i] + llist[j]:
                res += k - j
                prev = k
                break            
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right


def count(i, j):
    l1, l2 = L[i], L[j]
    low = l2 - l1
    high = l2 + l1
    start = bisect_right(L, low, j + 1)
    end = bisect_left(L, high, j + 1)
    return end - start


if __name__ == '__main__':
    input()
    L = [int(x) for x in input().split()]
    L.sort()
    total = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            total += count(i, j)
    print(total)

Submission status: Accepted

Solution code:
#D問題
import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        a,b = L[i],L[j]
        left = bisect.bisect_left(L,b-a+1)
        right = bisect.bisect_right(L,a+b-1)
        if i >= left and i <= right:
            ans-=1
        if j >= left and j <= right:
            ans-=1
        ans+=right-left

print(ans//3)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(len(L)-1):
  for j in range(i+1,len(L)):
    left=bisect.bisect_left(L, L[i]+L[j])
    if left > j:
      ans+=left-j-1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

n=int(input())
L=list(map(int,input().split()))
data=[0]*(10**3+2)
ans=0
pre=0
S=0
L.sort()
for i in range(1,n):

    l=L[i]
    S-=sum(data[pre:l+1])
    pre=l+1
    ans+=S
    for j in range(0,i):
        if l+L[j]<=10**3:
            data[l+L[j]]+=1
        S+=1
        # print('insert',l+L[j])

print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
l=list(map(int,input().split()))
l.sort()
# print(l)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        left=bisect.bisect_left(l,l[i]+l[j])
        # right=bisect.bisect_right(l,(l[i]+l[j]+1)//2)
        # print(left)
        # print(right)
        # print()
        cnt=left-(j+1)
        if left<=j+1:
            # print(99)
            continue
        # if right<j+2:
        #     cnt-=j+2-right
        if cnt>=0:
            ans+=cnt
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(sorted(map(int,input().split())))
cnt = 0
for j in range(1,N-1):
  k=j+1
  for i in range(j):
    while True:
      
      if k == N or S[i]+S[j] <= S[k]:
        k-=1
        break
      k+=1
    #print(i,j,k)
    #print(S[i],S[j], S[j+1:k+1],k-j)
    cnt += k-j
print(cnt)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = sorted(list(map(int, input().split())))

res = 0
for i in range(N):
    for j in range(i+1, N):
        idx = bisect.bisect_left(L, L[i]+L[j])
        res += max(0, idx-j-1)

print(res)

Submission status: Accepted

Solution code:
import bisect

def f(L):
    n = len(L)
    L.sort()

    count = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = L[i]
            b = L[j]
            start = max(a - b, b - a)
            end = a + b
            si = bisect.bisect_right(L, start)
            ei = bisect.bisect_left(L, end)
            zx = ei - si
            if i >= si and i < ei:
                zx -= 1
            if j >= si and j < ei:
                zx -= 1
            count += zx
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)

Submission status: Accepted

Solution code:
def CountTriangles( A): 
  n = len(A); 
  A.sort();  
  count = 0; 
  for i in range(n - 1, 0, -1): 
        l = 0; 
        r = i - 1; 
        while(l < r): 
            if(A[l] + A[r] > A[i]): 
                count += r - l;  
                r -= 1;  
            else:  
                l += 1;  
  print(count)
n=int(input())
l=[int(x) for x in input().split()]
CountTriangles(l)

Submission status: Accepted

Solution code:
def d_triangles():
    from itertools import combinations
    from bisect import bisect_right
    N = int(input())
    L = sorted([int(i) for i in input().split()])

    ans = 0
    for max_index in range(2, N):
        c = L[max_index]
        for second_index in range(max_index):
            b = L[second_index]
            other_index = bisect_right(L, c - b)
            if max_index > other_index:
                ans += max_index - other_index
                if other_index <= second_index:
                    ans -= 1
    return ans // 2

print(d_triangles())

Submission status: Accepted

Solution code:
import bisect
n=int(input())
List = [int(i) for i in input().split()]
List2=sorted(List)
ans = 0

for i in range(0,n-1): #aにたいし
  for j in range(i+1,n):
    #print(i,j)
    tmp1 = List2[i]
    tmp2 = List2[j]
    
    a=bisect.bisect_left(List2,tmp1+tmp2)
    ans += a -j-1
    #print(a,List2,tmp1,tmp2,j,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
Ans = 0
i = N - 1
j = i - 1
k = 0

newL = sorted(L)

while i >= 2:
  while j >= 1:
    min = newL[i] - newL[j]
    
    if k > j-1:
      break
    
    while k <= j - 1:

      if newL[k] > min:
        Ans = Ans + (j - k)
        pk = k
        break
      
      if k == j - 1:
        pk = k
        break      
     
      k = k + 1
      
    k = pk
    j = j - 1

  i = i - 1
  j = i - 1
  k = 0

print(Ans)

Submission status: Accepted

Solution code:
from bisect import*
N,*L=map(int,open(0).read().split());L.sort()
a=0
l=[]
r=[]
for i in range(1001):
    l.append(bisect_left(L,i))
    r.append(bisect(L,i))
for p in L:
    for q in L:
        x=p+q
        y=abs(p-q)
        a+=(l[x]if x<1001else N)-(r[y]if 0<y<1001else(y>1000)*N)
for p in L:
    x=2*p
    a-=3*(l[x]if x<1001else N)
print((a+2*N)//6)

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left
N = int(input())
L = list(map(int, input().split()))

L.sort()
cnt = 0
for i in range(N-1):
    for j in range(i):
        a, b = L[i], L[j] 
        r = bisect_left(L[i+1:], a+b) + i+1
        cnt += max(r - i - 1, 0)
            
print(cnt)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
arr = sorted([int(i) for i in input().split()])
c = (N * (N-1) * (N-2)) // 6
for i in range(N-1):
    for j in range(1, N-i):
        tmp = arr[i] + arr[i+j]
        idx = bisect.bisect_left(arr, tmp)
        #print(idx, arr[i], arr[i+j])
        c -= (N - idx)
print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for l in range(N):
    r = l+1
    while r<N:
        j = bisect_left(L, L[l]+L[r])
        ans += j-r-1
        r += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
res = 0
for i in range(N - 1, 1, - 1):
    for j in range(i - 1, 0, - 1):
        k = L[i] - L[j] + 1
        if k > L[j - 1]:
            break
        res += j - bisect.bisect_left(L, k)
print(res)

Submission status: Accepted

Solution code:
import bisect
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
  for j in range(n-1, i, -1):
    s = l[i]+l[j]
    ans += bisect_left(l[j+1:n], s)

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

chouhen = []
kosuu = 0

for i in range(N):
    for j in range(i+1, N):
        a, b = min(L[i], L[j]), max(L[i], L[j])
        chouhen.append((a, b))

L.sort()

for hen in chouhen:
    hidari = max(hen[0] - hen[1], hen[1] - hen[0])
    migi = sum(hen)

    hidari_idx = bisect.bisect_right(L, hidari)
    migi_idx = bisect.bisect_left(L, migi)

    # print(hidari, migi, hidari_idx, migi_idx)

    if L[hidari_idx] <= hen[0] <= L[migi_idx - 1]:
        kosuu -= 1
    if L[hidari_idx] <= hen[1] <= L[migi_idx - 1]:
        kosuu -= 1

    kosuu += migi_idx - hidari_idx

print(max(0, kosuu // 3))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n):
    for j in range(i+1,n):
        ma = max(l[i],l[j])
        mi = min(l[i],l[j])
        a = ma - mi + 1
        b = ma + mi - 1
        s = bisect.bisect_left(l,a)
        t = bisect.bisect_right(l,b)
        c = t - max(j+1,s + 1)
        if c <= 0:
            continue
        count += c
print(count)

Submission status: Accepted

Solution code:
n = int(input())
l = sorted([int(i) for i in input().split()])

from bisect import bisect_left
total = 0
for i in range(n):
    for j in range(i+1, n):
        total += (bisect_left(l, l[i] + l[j]) - j - 1)

print(total)

Submission status: Accepted

Solution code:
def countTriangles( A): 
    n = len(A); 
    A.sort();  
    count = 0; 
    for i in range(n - 1, 0, -1): 
        l = 0; 
        r = i - 1; 
        while(l < r): 
            if(A[l] + A[r] > A[i]):
                count += (r - l);
                r -= 1;  
            else:
                l += 1;  
    print(count); 
  
n=int(input())
l=list(map(int,input().split()))  
countTriangles(l)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a = list(map(int, input().split()))
new=sorted(a)
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        m=bisect.bisect_left(new,new[i]+new[j])
        ans+=(m-1)-j
print(ans)

Submission status: Accepted

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

L.sort()
#print(L)

cnt = 0
order =0
for i in range(N-2):
    highJ = 0
    for j in range(i+1,N-1):
        tmphighJ = max(j,highJ)
        for k in range(max(j+1,highJ+1),N):
            order+=1
            if L[k] < L[i]+L[j]:
                tmphighJ = k
            else:
                break
        highJ = max(j,tmphighJ)
        cnt+= highJ - j
        #print(i,j,highJ,cnt)

print(cnt)
#print(order)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        b = a[j+1:]
        tmp = a[i] + a[j] - 1
        tt = bisect.bisect_right(b,tmp)
        if tt > 0 :
            ans += tt
print(ans)

Submission status: Accepted

Solution code:
def d():
    n = int(input())
    ls = list(map(int, input().split()))
    ls.sort()
    count = 0
    for i in range(n-1):
        k = i + 2
        for j in range(i+1, n-1):
            while k < n and ls[i] + ls[j] > ls[k]:
                k += 1
            count += k - j - 1

    print(count)


if __name__ == '__main__':
    d()

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
L = read_ints()
L.sort()
# import numpy as np
# L = np.array(L)
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        # ここで二分探索するか
        cnt += bisect_left(L, a+b) - (j+1)
        # L_tmp = L[j+1:]
        # cnt += np.sum(L_tmp < b+a)

print(cnt)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
l=sorted(list(map(int,input().split())))
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        x=bisect.bisect_left(l,l[i]+l[j])
        cnt+=x-j-1
print(cnt)

Submission status: Accepted

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

def solve(N: int, L: "List[int]"):
    L.sort()
    answer = 0
    for i in range(N):
        for j in range(i+1,N):
            max_k = bisect.bisect_left(L,L[i]+L[j])
            answer += max_k-(j+1)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())
L = list(map(int, input().split()))
L.sort()
#print(L)

C = [0] * (L[-1] + 1)
num_list = []
for key, group in itertools.groupby(L):
    C[key] = len(list(group))
    num_list.append(key)

C_sum = list(itertools.accumulate(C))

ans = 0
for idx, a in enumerate(num_list):
    for b in num_list[idx:]:
        m = max(b - a + 1, L[0], b)
        M = min(b + a - 1, L[-1])
        val = 0
        if a == b and m == b:
            val = (C[a] * (C[a] - 1) * (C[a] - 2) // 6) + (C[a] * (C[a] - 1) // 2) * (C_sum[M] - C_sum[m])
        elif a == b and m > b:
            val = (C[a] * (C[a] - 1) * (C[a] - 2) // 6) + (C[a] * (C[a] - 1) // 2) *(C_sum[M] - C_sum[m] + C[m])
        elif a < b and m == b:
            val = C[a] * (C[b] * (C[b] - 1) // 2 + C[b] * (C_sum[M] - C_sum[m]))
        elif a < b and m > b:
            val = C[a] * (C[b] * (C_sum[M] - C_sum[m] + C[m]))

        #print('a={}, b={} --> {}<=c<={}, so +{}'.format(a, b, m, M, val))
        ans += val
print(ans)

Submission status: Accepted

Solution code:
def CountTriangles( A): 
  
    n = len(A); 
  
    A.sort();  
  
    count = 0; 
      
    for i in range(n - 1, 0, -1): 
        l = 0; 
        r = i - 1; 
        while(l < r): 
            if(A[l] + A[r] > A[i]): 
  
                # If it is possible with a[l], a[r] 
                # and a[i] then it is also possible 
                # with a[l+1]..a[r-1],a[r] and a[i] 
                count += r - l;  
  
                # checking for more possible solutions 
                r -= 1;  
              
            else: 
  
                # if not possible check for  
                # higher values of arr[l] 
                l += 1;  
    print(count); 
  
# Driver Code
n = int(input())
A = [int(x) for x in input().split()]
CountTriangles(A);

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
ans = 0
l.sort()

def bisec(i,k): #ギリギリokなj<=j_を探す
    ci = i
    ck = k
    i+=1
    k-=1
    j = int((i+k)/2)
    while k-i>1:
        if l[ci]+l[j]>l[ck]:
            k = j
            j = int((i+k)/2)
        else:
            i = j+1
            j = int((i+k)/2)
    if l[ci]+l[i]>l[ck]:
        return True,i
    elif l[ci]+l[i+1]>l[ck]:
        return True,i+1
    else:
        return False,-1

for i in range(n):
    for k in range(i+2,n):
        f,j = bisec(i,k)
        if f:
            ans += k-j
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
lengthnum = [0 for _ in range(max(L) + 1)]
m = len(lengthnum)

for l in L:
	lengthnum[l] += 1

for i in range(m - 1):
	lengthnum[i + 1] += lengthnum[i]
	
ret = 0
# print(L)
for s in range(N - 1):
	for b in range(s + 1, N):
		# print(L[s], L[b], lengthnum[min(L[-1], L[b] + L[s] - 1)] - lengthnum[L[b] - L[s]] - 1)
		ret += lengthnum[min(L[-1], L[b] + L[s] - 1)] - lengthnum[L[b] - L[s]] - 1
		if L[b] - L[s] < L[s]:
			ret -= 1
print(int(ret / 3))

Submission status: Accepted

Solution code:
n=int(input())
L=sorted(list(map(int,input().split())))
memo=[0]*2000
for l in L:
  memo[l-1]+=1
for i in range(1999):
  memo[i+1]=memo[i+1]+memo[i]
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    a=L[i]
    b=L[j]
    ans+=memo[a+b-2]-j-1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

L.sort()
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]
        add = a+b
        sub = abs(a-b)
        head = bisect_right(L, sub)
        tail = bisect_left(L, add)
        ex = 0
        if a > sub:
            ex += 1
        if b > sub:
            ex += 1
        ans += (tail - head - ex)

print(ans//3)

Submission status: Accepted

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

def calc(N, sticks):
    sums = [0 for i in range(1002)]
    for stick in sticks:
        for i in range(stick + 1):
            sums[i] += 1
    total = 0
    for i in range(N):
        for j in range(N):
            if i == j: continue
            a, b = sticks[i], sticks[j]

            lo = abs(b-a)+1
            hi = min(a+b, 1001)
            
            val = sums[lo] - sums[hi] - (lo <= a) - (lo <= b)
            if val <= 0: continue
            total += val
    return total // 6


print(calc(N, sticks))

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
count = 0
 
for i in reversed(range(N)):
  kmin = 0
  for j in reversed(range(i)):
    for k in range(kmin,j):
      if L[j] + L[k] > L[i]:
        count += j - k
        kmin = k
        break
        
print(count)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

import bisect

n = int(sys.stdin.readline().strip())
l = map(int, sys.stdin.readline().strip().split(" "))
l = sorted(l)
# pprint(l)

ans = 0
for i, l_i in enumerate(l[:-2]):
    for j, l_j in enumerate(l[:-1]):
        if j <= i:
            continue
        index = bisect.bisect_left(l, l_i + l_j)
        # print(l_i + l_j, index)
        # print("ij", i, j)
        ans += index - (j+1)
        
print(ans)