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

Solution (Python):
from bisect import bisect, bisect_left
import sys
from collections import defaultdict
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N = int(input())
L = sorted(inpl())
ans = 0

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

Solution (Python):
N = int(input())

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

L.sort()

def bisect(L,num,l,r):
    while r-l>1:
        if L[(r+l)//2] < num:
            l = (r+l)//2
        else:
            r = (r+l)//2
    return l

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        num = L[i]+L[j]
        if L[j+1]<num:
            if L[N-1]<num:
                ans+=N-1-j
            else:
                l = bisect(L,num,j+1,N-1)
                ans += l-j

print(ans)

Solution (Python):
import bisect

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

ans = 0
l = sorted(l)
for i in range(n):
    for j in range(i):
        tmp = 0
        nokori = l[i] - l[j]
        tmp = max(0, j - bisect.bisect_right(l, nokori))
        ans += tmp
print(ans)

Solution (Python):
import bisect

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

l.sort()

ans = 0

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

print(ans)

Solution (Python):

import sys
INF = float("inf")
from bisect import bisect_left


def solve(N: int, L: "List[int]"):
    
    L.sort()
    counter = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            k = bisect_left(L[j+1:], a+b)
            counter += k
    print(counter)
    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))  
    L = [int(next(tokens)) for _ in range(N)]  
    solve(N, L)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

L.sort()

import bisect

ANS=0
for i in range(N-1):
    for j in range(i+1,N):
        x=L[i]+L[j]

        r=bisect.bisect_right(L,x-1)

        ANS+=max(0,(r-j-1))

        

print(ANS)

Solution (Python):

from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from random import randint
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
import sys
import os
import re
sys.setrecursionlimit(9999)
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
N = 5001
 
'''
Check for special cases (n=1)
One wrong submission = 10 mins penalty!
do smth instead of nothing and stay organized
'''


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	
	for i in range(n):
		for j in range(i+1, n):
			a, b = arr[i], arr[j]
			c = a+b-1
			ind = bisect_right(arr, c, j+1, n) - j - 1
			
			total += ind
	print(total)


BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    l = LI()
    l.sort()
    ans = 0
    for i in range(n):
        a = l[i]
        for j in range(i):
            b = l[j]
            c = a+b
            k = bisect.bisect_left(l,c)-i-1
            ans += k
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from bisect import bisect_left
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()
    ans=0
    for i in range(1,n):
        for j in range(i+1,n):
            k=bisect_left(L,L[j]-L[i]+1)
            ans+=max(0,i-k)
    print(ans)
resolve()

Solution (Python):
import bisect

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

a.sort()

ans=0

for i in range(n-2):
    for j in range(i+1,n-1):
        under=a[i]+a[j]
        num=bisect.bisect_left(a,under)
        ans+=num-j-1

print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
l = LI()
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1,n):
        r = bl(l,l[i]+l[j])
        ans += (r-(j+1))
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

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

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

Solution (Python):
import bisect
N = int(input())
L = sorted([int(_) for _ in input().split()])

ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        ans += bisect.bisect(L, L[a] + L[b] - 1) - b - 1
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-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())

N = inp()
LL = inpl()
LL.sort()
ans = 0
for b in range(N):
    bL = LL[b]
    for a in range(b):
        aL = LL[a]
        cLmax = aL+bL
        ans += max(0,bisect.bisect_left(LL,cLmax)-b-1)

print(ans)

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left

n = ni()
l = list(li())

l.sort()

ans = 0

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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

from bisect import bisect_left

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

ans = 0
L.sort()
for i in range(N-2):
    for j in range(i+1, N-1):
        k = bisect_left(L, L[i]+L[j])
        ans += k - j - 1
print(ans)

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

L.sort()

def hersCode(L, n, a, b):
  
  
  ok = n
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[i] + L[j] > L[mid]:
      ok = mid
    else:
      ng = mid
  return ok - n

ans = 0
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    ans += hersCode(L, j, L[i], L[j])

print(ans)

Solution (Python):
import bisect

def solve():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    total = 0
    for s in range(N-2):
        for m in range(s+1, N-1):
            l = bisect.bisect_left(L, L[s] + L[m], 0, N)
            if l > m: total += l - m - 1
    print(total)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

ans = 0
for i in range(N)[::-1]:
    pos = 0
    for j in range(i)[::-1]:
        while pos < j and L[pos] <= L[i] - L[j]:
            pos += 1
        ans += j - pos
        if pos == j:
            break
print ans

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

from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)

Solution (Python):
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):
        ans += bisect.bisect_left(L, L[i]+L[j]) - 1 - j

print(ans)