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

K = [0] * (4 * (10 ** 3)+1)

K[L[0]+L[1]] = 1

count = 0

for i in range(2,N):
    count += sum(K[L[i]+1:])
    for j in range(i):
        K[L[j]+L[i]] += 1

print(count)

Submission status: Accepted

Solution code:
import bisect
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):
        Lij = L[i] + L[j]
        k = bisect.bisect_left(L, Lij)
        ans += max(k - j - 1, 0)
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):
    t=l[i]+l[j]-1
    index=bisect.bisect_right(l,t,j,n)
    ans+=max(0,index-j-1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
L = [int(c) for c in input().split()]
L.sort()
ans = 0
for i in range(N):
  for j in range(i+1, N):
    x = L[i]+L[j]
    ind = bisect_left(L, x)
    ans += ind-j-1
#    print(x,ind)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)

# print(L)
ans = 0
for i in range(n):
    # print(i)
    a = L[i]
    ci = n-1
    for j in range(i+1,n-1):
        b = L[j]
        ci = max(ci,j)
        # print("ci",ci)
        while ci > j and b+L[ci] <= a:
            ci -= 1
        ans += ci-j
print(ans)

Submission status: Accepted

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

import bisect
L.sort()
ans = 0
bl = bisect.bisect_left
br = bisect.bisect_right
for i,a in enumerate(L):
    for j,b in enumerate(L[i+1:],i+1):
        m = b-a+1
        M = b+a-1
        ans += br(L,M,j+1) - bl(L,m,j+1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = [int(_) for _ in input().split()]
l.sort()

res = 0
for i in range(n):
    for j in range(n):
        if i < j:
            res += bisect.bisect_left(l,l[i]+l[j]) - j -1

print(res)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for key_i,i in enumerate(l):
    for key_j,j in enumerate(l[key_i+1:]):
        key_j += key_i + 1
        ans += bisect.bisect_left(l, i+j) - key_j - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

ans = 0

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

Submission status: Accepted

Solution code:
from bisect import bisect,bisect_left

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

ans = 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,a+b)
        ans += k-j-1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
l=sorted(l)
n=len(l)
ans=0 
for i in range(n-1,0,-1):
    le=0 
    r=i-1 
    while le<r:
        if l[le]+l[r]>l[i]:
            ans=ans+(r-le)
            r-=1 
        else:
            le+=1 
print(ans)

Submission status: Accepted

Solution code:
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):
    for j in range(i+1,n):
        x=bisect.bisect_left(l[j+1:n],l[i]+l[j])
        ans+=x
print(ans)

Submission status: Accepted

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

ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        a=li[i]
        b=li[j]
        c=bisect.bisect_left(li,a+b)
        ans+=c-j-1
                  
print(ans)

Submission status: Accepted

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

# int(input())
# map(int, input().split())

from bisect import bisect_left

n = int(input())
a = tuple(sorted(map(int, input().split())))

ans = 0
for i in range(n):
    # 最大辺i
    for j in range(i):
        # 長さ中間の辺j
        min_k = a[i] - a[j] + 1
        # 最小辺が満たすべき最低限の長さ
        ans += max(0, j - bisect_left(a, min_k))
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(raw_input())
edges = list(map(int, raw_input().split(" ")))


def solve():
	edges.sort()
	ans = 0

	for i in range(len(edges)):
		for j in range(i+1, len(edges)):
			sum_of_two = edges[i] + edges[j]
			idx = bisect.bisect_left(edges, sum_of_two)

			if idx-1 > j:
				ans += idx-1-j
	return ans 
print(solve())

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
k = 0
for i in range(n):
    for j in range(i + 1, n):
        ind = bisect.bisect_left(l, l[i] + l[j])
        k += max(ind-j-1, 0)
print(k)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left, bisect_right

N = I()
L = III()

L.sort(reverse=True)
L2 = L[::-1]

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        p = bisect_right(L2,L[i]-L[j])
        if N-1-p-j>=0:
            ans += N-1-p-j

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
Ls = list(map(int, input().split()))
Ls.sort()
ans = 0
for i in range(N-2):
  li = Ls[i]
  idx = i
  for j in range(i+1, N-1):
    lj = Ls[j]
    while idx < N and li + lj > Ls[idx]:
      idx += 1
    ans += idx - j - 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
L=[int(i) for i in input().split()]
import bisect
L.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1
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,raw_input().split()))

print findnumberofTriangles(l)

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):
        x=l[i]+l[j]
        idx=bisect.bisect_left(l,x,j+1,n)
        count+=idx-j-1
        #print(idx,l[idx-1],x,idx-j-1)
print(count)

Submission status: Accepted

Solution code:
import bisect
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

N = int(sys.stdin.readline())
L = list(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]
        l = bisect.bisect_left(L, b - a + 1)
        r = bisect.bisect_left(L, b + a)
        ans += r - l - 1 - (b < a * 2)
print(ans // 3)

Submission status: Accepted

Solution code:
import bisect
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):
        c=bisect.bisect_left(l,l[i]+l[j])-(j+1)
        #print(c)
        ans+=c
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left

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):
        a = l[i]
        b = l[j]
        left = abs(a-b)
        right = a+b
        q = max(j+1, bisect_left(l, right))
        w = max(j+1, bisect_right(l, left))
        # left < c < right
        ans += q-w
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):
    for j in range(i):
        c = l[i]-l[j] + 0.01
        k = bisect.bisect_left(l,c)
        k = min(k,j)
        ans += (j-k)
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = list(sorted(map(int, input().split())))
s = 0
for i in range(N):
    for j in range(i+1, N):
        a, b = L[i], L[j]
        lc, rc = abs(a-b), a+b
        l = bisect.bisect_left(L, lc+1, j+1)
        r = bisect.bisect_left(L, rc, j+1)
        s += r - l
print(s)

Submission status: Accepted

Solution code:
import bisect
import math

N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        k = bisect.bisect_left(L, L[i]+L[j])
        # print(j, k)
        res += max(0, k-j-1)
print(res)

Submission status: Accepted

Solution code:
import bisect
#abs(a-b)<c<a+b
N=int(input())
L=sorted([int(i) for i in input().split()])
ans=0
#print(L)
for i in range(N):
    for j in range(i+1,N):
        A=bisect.bisect_left(L,L[i]+L[j])
        B=bisect.bisect_right(L,abs(L[i]-L[j]))
        tmp=A-B
        if B<=i<A:
            tmp-=1
        if B<=j<A:
            tmp-=1
        ans+=tmp
        #print(i,j,A,B,tmp)
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):

        mid = L[i]
        mini = L[j]

        ind = bisect.bisect_left(L,mid+mini)
        #print (mini,mid,ind)

        ans += ind - i - 1

print (ans)

Submission status: Accepted

Solution code:

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
#print(l)
def count(first,second):
    ok = second
    ng = n
    while ng-ok>1:
        mid = (ng+ok)//2
        if l[first]+l[second] > l[mid]:
            ok = mid
        else:
            ng = mid
    return ok - second

for first in range(n):
    for second in range(first+1,n):
        # thirdはfirst + second > third
        ans += count(first,second)

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from bisect import bisect_left


def solve(N: int, L: "List[int]"):
    # a<=b<=c
    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))  # 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 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(i,j,x,r,max(0,(r-j-1)))

print(ANS)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
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
	# print(arr)
	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
			# print(a, b, c, ind)
			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()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC143 D

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = sorted([int(_) for _ in input().split()])
#L[a] + L[b] > L[c]
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

L.sort()

def hersCode(L, n, a, b):
  #if L[-1] < n:
  #  return len(L)
  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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

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

def binary(mini,maxi,a,b): #a>b
  if maxi == mini + 1:
    if L[maxi] > a - b:
      return maxi
    elif L[mini] > a - b:
      return mini
    else:
      return False
  elif maxi == mini:
    if L[maxi] > a - b:
      return maxi
    else:
      return False
  else:
    mid = (mini+maxi)//2
    if L[mid] > a - b:
      return binary(mid,maxi,a,b)
    else:
      return binary(mini,mid,a,b)
      
for a in range(0, N-2):
  for b in range(a+1, N-1):
    tmp = binary(b+1, N-1, L[a], L[b])
    if tmp:
      ans += tmp - b
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

ans = 0
for i in range(len(l)):
    for j in range(len(l))[i + 1:]:
        k = bisect(l[j+1:], l[i] + l[j]) + j+1
        ans += len(l[j+1:k])
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tc = N
st = [j+1 for j in range(N-1)]
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        if j == tc:
            ans += tp
            break
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            tc = j 
            tp = (N-j-1) * (N-j) //2 #これをiの中でできないか
            ans += tp
            break
        start = st[j]
        if s <= l[start+1]:
            ans += start-j-1
            continue
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        st[j] = end
        ans += end-j-1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tp = N
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        if j == tc:
            ans += tp
            break
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            tc = j 
            tp = (N-j-1) * (N-j) //2 #これをiの中でできないか
            ans += tp
            break
        start = j+1
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        ans += end-j-1
print(ans)

Submission status: Runtime Error

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-2):
  a=L[i]
  for j in range(i+1,N-1):
    """
    b=L[j]
    lo=0
    hi=N
    x=a+b
    while lo<hi:
      mid=(lo+hi)//2
      if L[mid]<x: lo=mid+1
      else: hi=mid
    ans+=lo-(j+1) 
    """
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)

Submission status: Runtime Error

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())
arr=[int(x) for x in input().split()]
print(findnumberoftriangles(arr))

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
l = list(map(int,input().split()))
a = []
ans = 0

l.sort()
for i in range(n-1):
  if l[i] != l[i+1]:
    a.append(l[i])
if l[n-1] != l[n-2]:
  a.append(l[n-1])

if len(a) < 3:
  print("0")
else:
    b = list(itertools.combinations(a, 3))
    c = b[1]
    for j in range(len(b)):
      c = b[j]
      if c[1] < c[2] + c[0] and c[2] < c[1] + c[0] and c[0] < c[2] + c[1]:
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = 0

for i in range(N):
    L_count[L[i]] += 1

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

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
l = list(int(i) for i in input().split())
l = sorted(l, reverse=True)

cnt = 0

for i in range(n - 2):
    a = l[i]
    for j in range(i + 1, n-1):
        b = l[j]
        cnt += bisect.bisectright(l, a-b)-(j+1)

print(cnt)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
n = int(input())
l = list(int(i) for i in input().split())

cnt = 0

for bars in comb(l, 3, exact=True):
    a, b, c = bars[0], bars[1], bars[2]
    if a < b + c and b < a + c and c < b + a:
        cnt += 1

print(cnt)

Submission status: Runtime Error

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

cnt = 0

for i in range(n-1, -1, -1):
    for j in range(i-1, -1, -1):
        imin = 0
        imax = j-1

        while imin <= imax:
            mid = (imin + imax)//2
            if test[mid] + l[j] >= l[i]:
                imax = mid-1
            else:
                imin = mid+1

        cnt += j-imin

print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
L = map(int, input().split())
ans = 0
for c in range(N):
    for cc in range(c + 1, N):
        for ccc in range(cc + 1, N):
            ab = L[c]
            bb = L[cc]
            cb = L[ccc]
            if ab < (bb + cb) and bb < (ab + cb) and cb < (ab + bb):
                ans += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

ans=0
for a_idx in range(len(L)):
    a = L[a_idx]
    for b_idx in range(a_idx+1,len(L)):
        b = L[b_idx]
        c_low = b - a + 1
        c_up = a + b - 1
        
        c_low_idx = bisect.bisect(L,c_low)
        c_up_idx = bisect.bisect(L,c_up)
        c_low_idx = max(b_idx,c_low_idx)
        
        ans += max(0,c_up_idx-c_low_idx-1)
#         print(a,b,ans,c_up_idx,c_low_idx)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n = int(input())
l = sorted(list(map(int,input().split())))
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)