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:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
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(N):
    for j in range(i + 1, N):
        r = L[j] + L[i]
        ans += bisect.bisect_left(L[j+1:], r)
print(ans)

Submission status: Accepted

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

l.sort(reverse=True)
m = sorted(l)
#print(l)
# print(m)

import bisect

ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    x = a-b
    ind = bisect.bisect_right(m,x)
    #print(a, b, j, ind)
    if n-1-j-ind >= 0:
      ans += n-1-j-ind

print(ans)

Submission status: Accepted

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

count = 0
for i in range(N):
  z = 0
  for j in range(i + 1, N):
    x = L[i] + L[j]
    if z < N:
      while L[z] < x:
        z += 1
        if z == N:
          break
    count += z - j - 1
    #print(count)
print(count)

Submission status: Accepted

Solution code:
n = int(input())

sortedL = sorted(list(map(int, input().split())))

accum = [0] * (2*10**3)

prev_ind = 0
count = 0
for elm in sortedL:
    if prev_ind < elm:
        for i in range(prev_ind+1, elm):
            accum[i] = count
        count += 1
        accum[elm] = count
    else:
        count += 1
        accum[elm] = count
    prev_ind = elm

for i in range(prev_ind, 2*10**3):
    accum[i] = count

ans = 0
for i in range(n):
    for j in range(i+1, n):
        a, b = sortedL[i], sortedL[j]
        left = abs(a - b)
        right = a + b
        tmp = accum[right-1] - accum[left]
        if left < a < right:
            tmp -= 1
        if left < b < right:
            tmp -= 1
        
        ans += tmp

print(ans // 3)

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):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 長さじゃなくて、棒自体で区別してるやんけー！

import numpy as np

N = int(readline())
L = np.array(read().split(),np.int32)

L.sort()

U=1000
counter = np.bincount(L,minlength=U+U+10)
cum = counter.cumsum()

add = L[:,None] + L[None,:]
max_c = cum[add-1]
cnt_c = max_c - np.arange(len(L)) - 1

answer = np.triu(cnt_c,1).sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline


def main():
    N = int(input())
    L = [int(i) for i in input().split()]

    L.sort()
    ans = 0

    for i in range(N):
        for j in range(i):
            # a = bisect.bisect_right(L, L[i]+L[j])
            b = bisect.bisect_left(L, L[i]+L[j])
            # print(a, b)
            ans += max(0, b-i-1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    L=[int(x) for x in input().split()]
    L.sort()
    count=0

    dic={}

    for i in range(N):
        for j in range(i+1,N):
            if i:
                try:
                    start=dic[j]
                    count+=dic[j]-j-1
                except:
                    count+=N-j-1
                    continue
            else:
                start=j+1
            for k in range(start,N):
                if L[k]>=L[i]+L[j]:
                    dic[j]=k
                    break
                count+=1
                
                
                
    print(count)

main()

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
#print(l)
ans=0
if n==3:
  if l[0]+l[1]<=l[2]:
    ans=0
  else:
    ans=1
if n>=4:
  for lef in range(n-1):
    for ri in range(lef+1,n):
      idx=bisect.bisect_left(l,l[lef]+l[ri])
      ans+=idx-ri-1
#      print(lef,ri,idx,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
import bisect
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N = int(input())
L= inputs()
L.sort()
b= 0
ans = 0
for i in range(N-1,-1,-1):
    for j in range(i-1,-1,-1):
        b= L[i]-L[j]
        insert_index = bisect.bisect_right(L,b)
        #print(L,b,i,j,insert_index)
        ans += max(j-insert_index,0)
        #print(ans)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
L.sort()
for i in range(1, N):
    for j in range(i):
        ans += max(bisect.bisect_left(L, L[i] + L[j]) - i - 1, 0)

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):
    np = i
    for j in range(i + 1, N):
        idx = bisect.bisect_left(L, L[i] + L[j]) - 1
        cnt = idx - j
        if idx <= j or np > idx:
            continue
        res += cnt
        np = idx

print(res)

Submission status: Accepted

Solution code:
import bisect

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

L.sort()

res = 0

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

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def solve_d(n, l_list):
    res = 0
    l_list_s = sorted(l_list)
    h = []
    for i in range(1, n - 1):
        for j in range(0, i):
            heappush(h, l_list_s[i] + l_list_s[j])
        while len(h) > 0:
            a = heappop(h)
            if a > l_list_s[i + 1]:
                heappush(h, a)
                break
        res += len(h)

    return res


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    res = solve_d(n, l_list)
    print(res)


def test():
    assert solve_d(4, [3, 4, 2, 1]) == 1
    assert solve_d(3, [1, 1000, 1]) == 0
    assert solve_d(7, [218, 786, 704, 233, 645, 728, 389]) == 23


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

Submission status: Accepted

Solution code:
#import sys

#input = sys.stdin.readline

import bisect

def main():
#    h,w,a,b = map(int, input().split())
    n=int(input())
    l=list(map(int,input().split()))
    l=sorted(l)
 #   print(l)
    count=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            a = bisect.bisect_left(l,l[i]+l[j])
#            print(a)
            count+=a-j-1

    print(count)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
ans = 0

for i in range(N):
  for j in range(i+1,N):    
    A = L[i]+L[j]
    tmp = bisect.bisect_left(L,A)
    ans += tmp-j-1
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
from bisect import *

N=int(input())
L=list(map(int,input().split()))
h=[]
for i in range(N):
    heappush(h,L[i])
h2=[]
for i in range(N):
    heappush(h2,heappop(h))
s=0
for i in range(N):
    for j in range(N-1-i):
        bmc=h2[j+i+1]-h2[i]
        bpc=h2[j+i+1]+h2[i]
        a=-bisect_right(h2, bmc)+bisect_left(h2, bpc)-1
        if a>0:
            s+=a
            if bmc < h2[i]:
                s-=1
print(s//3)

Submission status: Accepted

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

ln.sort(reverse=True)

bcs = []
for i in range(1, n-1):
  row = []
  for j in range(i+1, n):
    row.append(ln[i] + ln[j])
  bcs.append(row)

cnt = 0
ix = [0 for _ in range(n-2)]
# a > b,c
for i in range(n-2):
  a = ln[i]
  for j in range(i, n-2):
    try:
      while ix[j] < (n - 2 - j) and bcs[j][ ix[j] ] > a:
        ix[j] += 1
    except:
      print(j, ix[j])
      exit()
  cnt += sum(ix[i:])
print(cnt)

Submission status: Accepted

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


L.sort(reverse=True)
dic = {}
cnt = 0

for i in range(1, N - 1):
    p = L[i]
    for j in range(i + 1, N):
        s = p + L[j]

        if s not in dic:
            dic[s] = 1
        else:
            dic[s] += 1

for i in range(N - 2):
    p = L[i]

    if i > 0:
        for x in range(i + 1, N):
            dic[p + L[x]] -= 1

    for key, value in dic.items():
        if key > p:
            cnt += value

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
ll = list(map(int,input().split()))
ll.sort()
ans = 0
for i in range(N-2):
    a = ll[0]
    b = 1
    for c in range(1,len(ll)-1):
        while (b<len(ll))and(ll[b]-ll[c] < a):
            b += 1
        ans += max(0,(b-c-1))
    del ll[0]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

n = int(input())
a = sorted(map(int, input().split()))
print(sum(j - bisect_right(a, a[i] - a[j], 0, j)
          for i in range(2, n) for j in range(1, i)))

Submission status: Accepted

Solution code:
import bisect

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

l.sort()
res = 0
for i in range(1, n - 1):
    b = l[i]
    for a in l[:i]:
        res += max(bisect.bisect_left(l, a + b) - (i + 1), 0)

print(res)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
l_list = sorted(map(int,input().split()))
ans = 0
#print(l_list)
for i in range(N):
    for j in range(i+1,N):
        sum_ij = l_list[i]+l_list[j]
        bi_num = bisect.bisect_left(l_list,sum_ij)
        #print(i,j,sum_ij,bi_num,bi_num-j)
        ans += bi_num-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
n = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        A = L[i] + L[j] - 1
        sa = abs(L[i] - L[j]) + 1
        big = bisect.bisect_right(L, A)
        sml = bisect.bisect_left(L, sa)
        num = big - sml
        if sa <= L[i] <= A:
            num -= 1
        if sa <= L[j] <= A:
            num -= 1
        if num > 0:
            ans += num
print(ans//3)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import*
n,*l=map(int,open(0).read().split())
l.sort()
A=0
for i in range(n):
    a=l[i]
    for j in range(i+1,n):
        b=l[j]
        k1=max(j+1,bisect(l,b-a))
        k2=bisect_left(l,a+b)
        A+=max(0,k2-k1)
print(A)

Submission status: Accepted

Solution code:
import fractions
import bisect
import math
import copy


N=int(input())
A=list(map(int,input().split()))
B=copy.copy(A)
A.sort(reverse=True)
B.sort()
total=0

for i in range(N):
    for j in range(i+1,N-1):
        x=bisect.bisect_right(B, A[i]-A[j])

        if N-j>x:
            total+=N-x-(j+1)
        #print(total,x,j)

print(total)

Submission status: Accepted

Solution code:
import bisect

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

total = 0
for i in range(len(ls)-1):
    for j in range(i+1, len(ls)):
        # k < i+j & k > j-i
        maxindex = bisect.bisect_left(ls, ls[i]+ ls[j], j+1)
        minindex = bisect.bisect_right(ls, ls[j]- ls[i], j+1)
        total += maxindex - minindex
            

print(total)

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            count += k - j
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

n = int(input())
a = sorted(map(int, input().split()))
r = 0
for i in range(2, n):
    j = i - 1
    while j and a[j - 1] + a[j] > a[i]:
        r += j - bisect_right(a, a[i] - a[j], 0, j)
        j -= 1
print(r)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = LIST()
L.sort()

ans = 0
for i in range(N-2):
	one = L[i]
	for j in range(i+1, N-1):
		two = L[j]
		val = one + two - 1
		idx = bisect(L, val)
		if idx-j <= 0:
			continue
		else:
			ans += (idx-j-1)
print(ans)

Submission status: Accepted

Solution code:

import bisect 

n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        a = l[i]
        b = l[j]
        k1 = bisect.bisect_left(l,a+b)
        ab = abs(a-b)
        k0 = bisect.bisect_right(l,ab)
        cnti = k1 - k0 
        if k0 <= i and i <= k1:
            cnti -= 1
        if k0 <= j and j <= k1:
            cnti -= 1       
        #print(a,b,cnti)
        cnt += cnti
print(cnt//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-2):
    for j in range(i+1,N-1):
        a=L[i]
        b=L[j]
        count+=bisect.bisect_left(L,a+b)-(j+1)
print(count)

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            count += k - j
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

l.sort()
count = 0
  
for i in range(0,n-2): 

    k = i + 2

    for j in range(i+1,n): 

        while (k < n and l[i] + l[j] > l[k]): 
            k += 1

        if(k>j): 
            count += k - j - 1

print(count)

Submission status: Accepted

Solution code:
import bisect
def main():

    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+2, N):
            a = L[i]
            c = L[j]
            k = bisect.bisect_left(L, c-a+1)
            if k <= i:
                ans += j-i-1
            else:
                ans += j-k
    return ans

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

Submission status: Accepted

Solution code:
def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count 

n = int(input())
ar = list(map(int, input().split()))
print(findnumberofTriangles(ar))

Submission status: Accepted

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

total = 0

for i in range(n-2):
    aI = arr[i]
    k = i + 2
    
    for j in range(i+1,n):
        mySum = aI+arr[j]

        while (k<n) and arr[k]<mySum:
            k+=1
            
        if k>j:
            total+= k-j-1

print(total)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
n = int(input())
L = list(map(int, input().split()))

L.sort()
# print(L)
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        A = L[i] + L[j] - 1
        sa = abs(L[i] - L[j]) + 1
        big = bisect.bisect_right(L, A)
        sml = bisect.bisect_left(L, sa)
        num = big - sml
        if sa <= L[i] <= A:
            num -= 1
        if sa <= L[j] <= A:
            num -= 1
        # print(L[i], L[j])
        # print(sml, big, num)
        # print(num)
        if num > 0:
            ans += num
        # print(sa, A, L)
        # print(sml, big)
        # print(dab)
print(ans//3)


# print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a = sorted(a)
def trian(a):
    n=len(a)
    res = 0
    for x in range(n):
        z=x+2
        for y in range(x+1,n):
            while(z<n and a[x]+a[y]>a[z]):
                z+=1
            res += z-y-1
    return res
print(trian(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=input()
L=tuple(map(int,input().split()))
l=[0]*1001
g=[0]*1001
for i in L:
    l[i]+=1
for i in range(1,1001):
    g[i]=g[i-1]+l[i]
a=0
for i in range(1,999):
    for j in range(i+1,1000):
        a+=l[i]*l[j]*(g[min(i+j-1,1000)]-g[j])
for i in range(1,1001):
    if l[i]>1:
        t=l[i]*(l[i]-1)//2
        for j in range(1,i):
            a+=t*l[j]
        if l[i]>2:
            a+=t*(l[i]-2)//3
        for j in range(i+1,min(1001,i*2)):
            a+=t*l[j]
print(a)

Submission status: Accepted

Solution code:
# import numpy as np
N=int(input())
L=list(map(int, input().split()))
L.sort()
ans=0
for i in range(N-2):
    k=i+2
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        while(L[k]<l):
#           print(i,j,k)
            k+=1
            if k==N:
                break
        k-=1
        ans+=k-j
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# 2辺の和リスト
d = [0] * (l[-1] * 3)
ans = 0

for i in range(n):
  for val in d[l[i] + 1:]:
    # 長さd[i]より小さい組み合わせはOK
    ans += val

  # 自身との組み合わせをdに追加
  for j in range(i):
    d[l[i] + l[j]] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
L = map(int,raw_input().split())

L = sorted(L)
ans = 0

for a in xrange(n-2):
	c = a+2
	for b in xrange(a+1,n-1):
		while c < n and L[a] + L[b] > L[c]:
			c += 1
		if c > b:
			ans += (c-b-1)
print ans

Submission status: Accepted

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

N = int(input())
L = [int(i) for i in input().split()]
total = 0

L = sorted(L)

for i in range(N-2):
    k = i + 2
    for j in range(i+1, N):
        while k < N and L[i] + L[j] > L[k]:
            k+=1
        if k > j:
            total += k-j-1

print(total)

Submission status: Accepted

Solution code:
import bisect

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

L.sort()
ans=0

for i in range(N-1):
	for g in range(i+1, N-1):
		bigger = bisect.bisect_left(L, L[i]+L[g])
		ans += bigger - g -1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
L2 = L[::-1]
ans = 0
for i in range(N):
    long = L2[i]
    for j in range(i + 1, N):
        d = long - L2[j]
        ans += max(N - 1 - j - bisect.bisect_right(L[:N - j], d), 0)

print(ans)

Submission status: Accepted

Solution code:
def findnumberofTriangles(arr): 
  
    n = len(arr) 
    arr.sort() 
    count = 0
  
    for i in range(0,n-2): 
   
        k = i + 2
  
        for j in range(i+1,n): 
  
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
  
    return count 

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

print(findnumberofTriangles(L))

Submission status: Accepted

Solution code:
N = int(input())

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

lList.sort()
counter = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        ab = lList[a] + lList[b]
        startIndex = b+1
        endIndex = N-1
        while endIndex - startIndex > 1:
            searchIndex = (startIndex+endIndex)//2
            if lList[searchIndex] >= ab:
                endIndex = searchIndex
            else:
                startIndex = searchIndex
        if lList[startIndex] >= ab:
            counter += 0
        elif lList[endIndex] < ab:
            counter += N-1-b
        else:
            counter += startIndex - b

print(counter)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
l_copy = l.copy()
l_copy = l_copy[::-1]

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        rest = l_copy[i] - l_copy[j]
        ind = bisect.bisect_right(l, rest)
        ind = n - ind - 1
        if ind <= j:
            break
        else:
            ans += ind - j

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right as binser
n = int(input())
l = [int(j) for j in raw_input().split()]
l = sorted(l)
ans = 0 
for i in range(1,n):
    for j in range(i):
        a = l[i] - l[j]
        x = binser(l,a, j+1, i)
        # if i-x:
        #     print(x, j+1, i-1)
        if l[x] == a:
            x = x+1
        ans+=(i-x)
        # print(i-x, a, l[x], l[j], l[i])
        # print(l[x], l[i],l[j])
print(ans)

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools
from bisect import bisect_left

# ひとつ入力
n = int(input())

# 空白区切りの数列をリストに代入
l = [int(i) for i in input().split()] 

l=sorted(l)

#print(l)
answer = 0
for i in range(n-1,1,-1):
    for j in range(i-1,0,-1):
        k = bisect_left(l,l[i]-l[j]+1)
        if(l[j]>=l[k]):
            answer += max(j-k,0)
#            print(i,j,k,l[i],l[j],l[k])


print(answer)

Submission status: Accepted

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

L = sorted(L)

mappin = [0] * 2001
for l in L:
    mappin[l] += 1

for i in range(2000):
    mappin[i + 1] += mappin[i]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        temp = L[i] + L[j]
        addd = mappin[temp - 1] - j - 1
        # print(str(i) + " " + str(j))
        # print(addd)
        ans += max([0, addd])


print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
L = inpl()
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        k = bisect_left(L,L[i]+L[j],j,N) - (j+1)
        ans += k
print(ans)

Submission status: Accepted

Solution code:


def find(arr):

	n = len(arr)
	arr.sort()
	count = 0
	for i in range(0,n-2):

		k = i + 2

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

	return count

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


print(find(a))

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0

for i in range(N-2):
    for j in range(i + 2,N):
        cnt += min(j - bisect.bisect_left(L,L[j] - L[i] + 1), j - i - 1)
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
def main():
    n = int(input())
    d = [int(x) for x in input().split()]
    d = sorted(d)
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            flgi,flgj = 0,0
            a = d[i]+d[j]
            b = d[j]-d[i]

            left = bisect_left(d,a)
            right = bisect_right(d,b)
 
            if right<i+1<=left:
                flgi = 1
            if right<j+1<=left:
                flgj = 1
            ans += max((left-right)-(flgi+flgj),0)
    print(ans//3)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num = int(input())
    data = list(map(int, input().split()))

    data.sort()
    dp = [0 for i in range(max(data) * 2 + 1)]

    count = Counter(data)

    for i in range(1, max(data) * 2 + 1):
        dp[i] = dp[i - 1] + count[i]

    count = sorted(count.items(), key=lambda x: x[0])
    ans = 0

    # print(data)
    # print(count)
    # print(dp)

    for i in range(len(count)):
        if count[i][1] >= 3:
            ans += (count[i][1] * (count[i][1] - 1) * (count[i][1] - 2)) // 6
        if count[i][1] >= 2:
            nokori = count[i][0] * 2 - 1
            ans += (count[i][1] * (count[i][1] - 1)) // 2 * (dp[nokori] - dp[count[i][0]])

        for j in range(i + 1, len(count)):
            if count[j][1] >= 2:
                ans += count[i][1] * (count[j][1] * (count[j][1] - 1)) // 2
            max_data = count[i][0] + count[j][0] - 1
            kari = count[i][1] * count[j][1] * (dp[max_data] - dp[count[j][0]])
            ans += kari

    print(ans)








if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
cnt = [0]*(3*10**3+1)
for i in range(N):
    cnt[L[i]] += 1
cum = [0]*(3*10**3+1)
for i in range(3*10**3):
    cum[i+1] = cum[i]+cnt[i+1]

ans = 0
for a in range(1,10**3+1):
    if cnt[a] == 0:
        continue
    for b in range(a+1,10**3+1):
        if cnt[b] == 0:
            continue
        ans  += (cum[a+b-1]-cum[b])*cnt[a]*cnt[b]

for a in range(10**3+1):
    if cnt[a] < 2:
        continue
    ans += ((cum[2*a-1]-cnt[a])*cnt[a]*(cnt[a]-1))//2

for a in range(10**3+1):
    if cnt[a] < 3:
        continue
    ans += (cnt[a]*(cnt[a]-1)*(cnt[a]-2))//6

print(ans)

Submission status: Accepted

Solution code:
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(i+1,N):
        a = L[i]
        b = L[j]
        ans += bisect_left(L[j+1:], a+b)
print(ans)

Submission status: Accepted

Solution code:
import sys
inf = float("inf")
from bisect import bisect_left,bisect_right

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n = int(input())
Arr = get_array()
Arr.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        new = Arr[i]+Arr[j]
        ans+=bisect_left(Arr[j+1:], new)
print(ans)

Submission status: Accepted

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


N = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
ans = 0
di = collections.defaultdict(lambda :0)
for i in range(N):
    for j in range(i+1,N):
        key = nums[i] + nums[j]
        di[key] += 1
co = 0
for k,v in di.items():
    for temp in nums:
        if k <= temp:
            co += v

temp = combinations_count(N,3)
print(temp- co)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    d=list(map(int,input().split()))
    d.sort(reverse=True)
    
    #print(d)
    
    ans=0
    for large in range(0,n-2):
        presmall=n-1
        for middle in range(large+1,n-1):
            if d[large]<d[middle]+d[presmall]:
                ans+=presmall-middle
                #print(d[large],d[middle],d[presmall],"   ",d[presmall]+d[middle],presmall)
            else:
                flag=False
                for i in range(presmall-1,middle,-1):
                    #print(presmall)
                    if d[large]<d[middle]+d[i]:
                        presmall=i
                        flag=True
                        break
                if flag==False:
                    break
                else:
                    ans+=presmall-middle
                    #print(d[large],d[middle],d[presmall],"   ",d[presmall]+d[middle],presmall,"#")
    print(ans)
main()