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: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right
l.sort()
ans = 0
for i in range(len(l)):
    for j in range(i+1, len(l)):
        c_min = l[j] - l[i]
        c_max = l[i] + l[j]
        tmp = l[j+1:]

        idx_min = bisect_left(tmp, c_min)
        idx_max = bisect_left(tmp, c_max)

        if idx_min < len(tmp) and tmp[idx_min] == c_min:
            idx_min += 1

        ans += max(0, idx_max - idx_min)

print(ans)

Submission status: Time Limit Exceeded

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

def ok(a, b, c):
    return a < b + c and b < a + c and c < a + b

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,*l=map(int,open(0).read().split())
print(sum(a<b+c and b<c+a and c<a+b for a,b,c in itertools.combinations(l, 3)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = 0
for a in range(n):
    for b in range(a+1, n):
        for c in range(b+1, n):
            if dat[a] < (dat[b] + dat[c]) and dat[b] < (dat[c] + dat[a]) and dat[c] < (dat[a] + dat[b]):
                res += 1
print(res)

Submission status: Time Limit Exceeded

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

works= lambda a,b,c : (a<(b+c)) and (b<(a+c)) and (c<(b+a))

total = 0

for i in range(n):
    aI = arr[i]
    for j in range(i+1,n):
        aJ = arr[j]
        for k in range(j+1,n):
            if works(arr[k],aI,aJ):
                total+=1
            else:
                break

print(total)

Submission status: Time Limit Exceeded

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

Ls.sort()
S = 0
for i in range(N - 2):
    A = Ls[i]
    for j in range(i + 1, N - 1):
        B = Ls[j]
        for k in range(j + 1, N):
            C = Ls[k]
            if A + B <= C:
                break
            else:
                S += 1
print(S)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
l = list(map(int, input().split()))
ll = list(itertools.combinations(l, 3))
ans = 0
for a, b, c in ll:
  if a < b+c and b < c+a and c<a+b:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n=int(input())
l=[int(i) for i in input().split()]

ans=0
for i,j,k in permutations(l,3):
    if i<j+k and j<i+k and k<i+j:
        ans+=1
print(ans//6)

Submission status: Time Limit Exceeded

Solution code:
def main():
	import sys
	input = sys.stdin.readline
	
	n = int(input())
	arr = sorted(map(int, input().split()))
	
	ans = 0
	for i in range(2, n):
		for l in range(i - 1):
			r = l + 1
			while arr[l] + arr[r] <= arr[i]:
				r += 1
			
			ans += i - r
	
	print(ans)
	
	return 0

main()

Submission status: Time Limit Exceeded

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

works= lambda a,b,c : (a<(b+c)) and (b<(a+c)) and (c<(b+a))

total = 0

for i in range(n):
    aI = arr[i]
    for j in range(i):
        aJ = arr[j]
        for k in range(j):
            if works(arr[k],aI,aJ):
                total+=1

print(total)

Submission status: Accepted

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)
ans = 0
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: Accepted

Solution code:
import bisect
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):
        num = L[i] + L[j]
        ind = bisect.bisect_right(L,num - 1)
        if ind > j - 1:
            ans += ind - j - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

def binary_search(items, a, b, i, j):
    def c_is_x(c):
        is1 = c > max(a - b, b - a)
        is2 = c < a + b

        if is1 and is2:
            return 0
        elif is1:
            return 1
        else:
            return 2

    low = j+1
    high = len(items) - 1

    while low <= high:
        mid = (low + high) // 2
        ans = items[mid]
        c_type = c_is_x(ans)
        if c_type == 0 and mid != i and mid != j:
            return mid
        elif c_type == 1:
            low = mid + 1
        else:
            high = mid - 1

    return None


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

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

        if k < N:
            c = L[k]
            # print(a, b, c, a+b)
            # print(i, j, k)
            count += max(k - j, 0)


print(count)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a, b = L_list[i], L_list[j]
        r = bisect_left(L_list, a+b)
        ans += max(0,r-j-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):
    res=l[i]+l[j]
    ans+=bisect.bisect_left(l,res)-1-j
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-1):
    b = l[:i]
    c = l[i+1:]
    for j in b:
        ans += bisect.bisect_left(c, l[i] + j)#2番目の棒より短く(left), 一定以上の長さを持つ([i+1:])
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from bisect import bisect_left
def main():
    n, *l = map(int, read().split())
    l.sort()
    r = n * (n - 1) * (n - 2) // 6
    for i1 in range(n - 2):
        for i2 in range(i1 + 1, n - 1):
            r -= (n - bisect_left(l, l[i1] + l[i2]))
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  k=i
  for j in range(i+1,n):
    while k<n and l[k]<l[i]+l[j]:
      k+=1
    ans+=k-(j+1)
print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import bisect

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += (bisect.bisect_left(arr,c,j+1) - j - 1)
            #ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import bisect
def resolve():
    n = int(input())
    l = sorted(list(map(int,input().split())))
    ans = 0
    for a in range(n):
        for b in range(a+1,n):
            c = bisect.bisect_left(l,l[a]+l[b])
            if c > b:
                ans += c-b-1
            else:
                pass
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = sorted([int(n) for n in input().split()])
#print(L)

count = 0
for i in range(N-1):
    b = L[:i]
    c = L[i+1:]
    for j in b:
        count += bisect.bisect_left(c, L[i] + j)

print(count)

Submission status: Accepted

Solution code:
n = int(input())
import bisect
a = sorted(list(map(int, input().split(" "))))
ans = 0
for i in range(1, n-1):
  b = a[:i]
  c = a[i + 1:]
  #print(b, c)
  for j in b:
    ans += bisect.bisect(c, a[i]+j-0.1)
    #print(bisect.bisect(c, a[i]+j-0.1))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
N=int(input())
A=list(map(int, input().split()))
A.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        a,b=A[i],A[j]
        B=A[j+1:]
        l=abs(a-b)
        r=a+b
        # print(bisect_left(B,r)-bisect_right(B,l))
        ans+=bisect_left(B,r)-bisect_right(B,l)
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
L = sorted(list(map(int,input().split())))
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        tmp = bisect_left(L,L[i]+L[j])
        cnt += tmp - j - 1

print(cnt)

Submission status: Accepted

Solution code:
from bisect import *

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

cnt = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        k = bisect_left(l, a+b)
        cnt += k-(j+1)
print(cnt)

Submission status: Accepted

Solution code:
import bisect


def main():
    n = int(input())
    l_lst = list(map(int, input().split()))
    l_lst.sort()

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):

            a = l_lst[i]
            b = l_lst[j]
            tmp = bisect.bisect_left(l_lst, a + b)
            tmp -= j + 1
            tmp = max(0, tmp)
            count += tmp

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ans = 0
    for a_idx in range(N-2):
        for b_idx in range(a_idx+1, N-1):
            l_idx = b_idx + 1
            r_idx = bisect.bisect_left(L, L[a_idx] + L[b_idx])
            ans += r_idx - l_idx
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

# 二分探索
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        a, b = L[i], L[j]
        # c < a + b
        r = bisect_left(L, a+b)
        l = j+1
        cnt += max(0, r-l)
print(cnt)

Submission status: Accepted

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

ans = 0
for i, a in enumerate(L[2:]):
    k = i + 1
    for j, b in enumerate(L[:i + 2]):
        while j < k and a - b < L[k]:
            k -= 1
        ans += i - max(k, j) + 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline
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):
        l = L[i] + L[j]
        p = bisect.bisect_left(L, l)
        # print(p)
        ans += p - j - 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
  for j in range(i+1,n):
    l=j;r=n
    while abs(l-r)>1:
      mid=(r+l)//2
      if L[i]<L[j]+L[mid] and L[j]<L[i]+L[mid] and L[mid]<L[i]+L[j]:
        l=mid
      else: r=mid
    ans+=l-j
print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)



N = int(input())
A = list(map(int,input().split()))
A.sort()
M = pow(10,6)+ 100
Tree = BIT(M)
for x in A:
  Tree.add(x,1)
ans = 0
for i in range(N):
  for j in range(i+1,N):
    x = A[i]; y = A[j]
    Tree.add(x,-1);Tree.add(y,-1)
    MIN = abs(x-y)+1; MAX = (x+y)-1
    #print(x,y,MIN,MAX)
    ans += Tree.get(MIN,MAX)
    Tree.add(x,1);Tree.add(y,1)
    #print(ans)
print(ans//3)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

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):
        b = L[i]
        c = L[j]
        M = L[i+1:j]
        ans += bisect_right(M, b + c - 1) - bisect_right(M, c - b)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

ans = 0
for small in range(n - 2):
    for mid in range(small + 1, n - 1):
        div = bisect_left(arr, arr[small] + arr[mid], 0, n)
        if div > mid + 1:
            ans += div - mid - 1

print(ans)

Submission status: Accepted

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

L.sort()

res=0
for i in range(N):
    for j in range(N):
        if not i<j:
            continue
        m=abs(L[i]-L[j])
        M=L[i]+L[j]
        r=bl(L,M)-br(L,m)
        if m<L[i]<M:
            r-=1
        if m<L[j]<M:
            r-=1
        res+=r
print(res//3)

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

import bisect

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

Submission status: Accepted

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

cnt = 0
# a の index
for a in range(len(L)):
    # b の index
    for b in range(a+1,len(L)):
        # c が取りうる最大の index
        c_idx = bisect.bisect_left(L,L[a]+L[b]) - 1
        cnt += c_idx - b
print(cnt)

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

Submission status: Accepted

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


def solve(N: int, L: "List[int]"):
    from itertools import combinations
    from bisect import bisect_left as bl
    L = sorted(L)
    ans = 0
    for ai, a in enumerate(L):
        for bi, b in enumerate(L[ai+1:-1], ai+1):
            ci = bl(L, a+b)
            ans += ci - bi - 1
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, L))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
from bisect import *
N = int(input())
L = sorted(map(int,input().split()))
a = 0

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

Submission status: Accepted

Solution code:
import bisect


def LI():
    return list(map(int, input().split()))


N = int(input())
L = LI()
L.sort()
ans = 0
for i in range(N-1, 1, -1):
    for j in range(i-1, 0, -1):
        ind = bisect.bisect_right(L, L[i]-L[j])
        if ind < j:
            ans += j-ind
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
import bisect


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


def input_int():
    return int(input())


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


def main():
    n = input_int()
    L = sorted(input_int_list())
    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            idx = bisect.bisect_left(L, L[i] + L[j])
            ans += idx - j - 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int, input().split()))
L.sort()
#print(L)
import bisect
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])
        #print(i, j, k)
        ans += max(0, k-j-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left


N, *L = map(int, open(0).read().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]
        ans += bisect_left(L, a + b, lo=j + 1) - (j + 1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

ans = 0
for a in range(0,n):
    for b in range(a+1,n):
        p = bisect.bisect_left(L, L[a]+L[b])
        ans += max(p-(b+1),0)
        
print(ans)

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	L = [int(l) for l in input().split(" ")]
	L.sort()
	m = len(L)
	cnt = 0
	for i in range(m):
		k = m - 1
		for j in range(i + 1, m):
			while m + i - j < k:
				if L[m + i - j] + L[i] <= L[k]:
					k -= 1
				else:
					cnt += k - m - i + j
					break
	print(cnt)

main()

Submission status: Accepted

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

L.sort()

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

print(count)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N = I()
    L = sorted(LI())
    ans = 0

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N = I()
    L = sorted(LI())
    ans = 0

    for i in range(N):
        for j in range(i+1, N):
            a, b = L[i], L[j]
            # print(L[j+1:], abs(a - b), a+b, bisect_left(L[j+1:], abs(a - b)), bisect_left(L[j+1:], a + b))
            ans += bisect_left(L[j+1:], a + b) - bisect_left(L[j+1:], abs(a - b))

    print(ans)

if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
from bisect import bisect_left


def can_make_tri(a, b, c):
    return a < b + c and b < c + a and c < a + b


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

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-2):
    for j in range(i+1,N-1):
        x=L[i]+L[j]
        ans+=(bisect.bisect_left(L,x)-j-1)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n, *l = map(int, open(0).read().split())
l.sort()

print(sum(bisect_left(l, l[i] + l[j]) - 1 - j for i in range(n)
          for j in range(i + 1, n)))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n, *l = map(int, open(0).read().split())
l.sort()

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n = I()
L = readInts()
L = sorted(L)
# 1,2番目を特定する
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = L[i]
        b = L[j]
        c = bisect.bisect_left(L, a + b)
        ans += c - (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):
        ans+=bisect.bisect_left(l,l[i]+l[j])-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):
        x=bisect.bisect_left(l,l[i]+l[j])-j-1
        ans+=max(0,x)
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect

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

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        a, b = L[i], L[j]
        c_l = bisect.bisect_left(L, a + b)
        
        if c_l <= j:
            continue
        
        # print(i, j, c_l)
        res += c_l - (j + 1)

print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_right,bisect_left
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):
        a = L[i]
        b = L[j]
        indU = bisect_left(L,a+b)
        indL = bisect_right(L,b-a)
        if j<indU and i>= indL:
            cnt += indU-indL-2
        elif indL<=i<indU and j>=indU or i<indL and indL<=j<indU:
            cnt += indU-indL-1
        elif j<indL or i>=indU:
            cnt += indU-indL
print(cnt//3)

Submission status: Accepted

Solution code:
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      k = bisect.bisect_left(LS,LS[i]+LS[j])
      ans += k-j-1
print(ans)

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):
        x = L[i] + L[j]
        y = bisect_left(L, x)
        ans += y - j - 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
from copy import deepcopy
N = int(input())
L = sorted(map(int, input().split()))

ans = 0
for i in range(N):
    for j in range(i + 1, N - 1):
        b = L[j] + L[i]
        x = bisect.bisect_left(L, b) - j - 1
        if x > 0:
            ans += x

print(ans)

Submission status: Accepted

Solution code:
import bisect


def LI():
    return list(map(int, input().split()))


N = int(input())
L = LI()
L.sort()
ans = 0

for i in range(N-1, 1, -1):
    for j in range(i-1, 0, -1):
        xl = L[i]-L[j]
        ind = bisect.bisect_right(L, xl)
        if j > ind:
            ans += j-ind
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
n, *l = map(int, open(0).read().split())
l.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        a = l[i]
        b = l[j]
        # a - b < c
        # b - a < c
        # c < a + b
        # max(a - b, b - a) < c < a + b
        right = bisect_left(l, a + b)
        left = bisect_right(l, max(a - b, b - a))
        tmp = max(0, right - left)
        if left <= i < right:
            tmp -= 1
        if left <= j < right:
            tmp -= 1
        ans += tmp
print(ans // 3)