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 = sorted(L)

def binary_search(func, array, left=0):
    right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    if y_left==False:return 0
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

SUM = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    l = L[i]+L[j]
    if L[-1]<l:
      k = N-1
    else:
      k = binary_search(lambda x: x<l, L, j+1)
    SUM += max(0,k-j)

print(SUM)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = sorted(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])
        if k > j:
            ans += k - j - 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://takeg.hatenadiary.jp/entry/2019/11/22/212816
# https://drken1215.hatenablog.com/entry/2019/10/20/032700

import bisect

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ret = 0
    for a in range(N-2):
        for b in range(a+1,N-1):
#            a<b+c => a-b<c
#            b<c+a => b-a<c
#            c<a+b
# b-a<c<a+b
            rr = bisect_right(L[b+1:], L[a]+L[b]-1)
            ll = 0
            ret += rr - ll

    print(ret)

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-1, 1,-1):
    for j in range(i-1,0,-1):
        x = L[i]-L[j]
        maxindex = bisect.bisect_right(L, x)
        if j>maxindex:
            ans += j-maxindex

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left

def solve():
    n = int(input())
    l = [int(x) for x in input().split()]
    l.sort()
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            r = bisect_left(l, l[i] + l[j])
            # if r > j:
            ans += r - j - 1
    print(ans)

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left

def solve():
    n = int(input())
    l = [int(x) for x in input().split()]
    l.sort()
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            r = bisect_left(l, l[i] + l[j])
            if r > j:
                ans += r - j - 1
    print(ans)

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""

Submission status: Accepted

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

L.sort()
ans=0

#a<b<c,a+b>c
for b in range(n):
    for a in range(b):
        ab=L[a]+L[b]
        r=bisect.bisect_left(L,ab)
        l=b+1
        #print("a=" + str(a) + "b=" +str(b))
        ans+=max(0,r-l)

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0          
for ai in range(n):
  for bi in range(ai+1,n):
    ci = bisect.bisect_left(l,l[ai]+l[bi])
    if ci>bi:
      ans += ci-bi-1
print(ans)

Submission status: Accepted

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

L = sorted(L)

import bisect

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

print(count)

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+1
    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:
n = int(input())
ls = list(map(int, input().split()))
rsw = [0]*1005
for i in ls:
    rsw[i] += 1
for i in range(1,1005):
    rsw[i] = rsw[i-1] + rsw[i]
res = 0
for i in range(n):
    for j in range(i+1,n):
        a = ls[i]
        b = ls[j]
        low = abs(a-b)
        high = a+b
        tmp = rsw[min(high,1004)-1] - rsw[low]
        if low < a < high:
            tmp -= 1
        if low < b < high:
            tmp -= 1
        res += tmp
print(res//3)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
from sys import stdin
input = stdin.readline


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

  # dic = defaultdict(int)
  # for l in L:
  #   dic[l] += 1
  # uniq = sorted(dic.keys())
  # sum_ = [0]*(uniq[-1]+1)
  # for i in range(1, uniq[-1]+1):
  #   sum_[i] = sum_[i-1] + dic[i]
  L = sorted(L)

  ans = 0
  for i in range(N):
    for j in range(i+1, N):
      if i == j:
        continue
      a = L[i]
      b = L[j]
      # lower = bisect.bisect_right(L[:i]+L[i+1:j]+L[j+1:], abs(a-b)) - 1
      # upper = bisect.bisect_right(L[:i]+L[i+1:j]+L[j+1:], a+b) - 1
      lower = bisect.bisect_right(L, abs(a-b), lo=j+1, hi=len(L)) - 1 - (j+1)
      upper = bisect.bisect_left(L, a+b, lo=j+1, hi=len(L)) - 1 - (j+1)
      # lower = bisect.bisect_right(L[j+1:], abs(a-b)) - 1
      # upper = bisect.bisect_left(L[j+1:], a+b) - 1

      # print(a, b, lower, upper)
      # print(f'--> {L[j+1:]}')

      # if lower < 0 or upper < 0: continue
      if upper < 0: continue
      ans += (upper - max(lower, 0) + 1)

  # print(dic)
  # print(uniq)
  # print(sum_)
  print(ans)


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

Submission status: Accepted

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

import bisect
ans = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

L.sort()
from bisect import*
i=0
ans=0
while i<N:
    j=i+1
    while j<N:
        ans+=bisect_left(L,L[i]+L[j])-j-1
        j+=1
    i+=1

print(ans)

Submission status: Accepted

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

L.sort()
from bisect import*
i=0
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=bisect_left(L,L[i]+L[j])-j-1

print(ans)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools,copy,bisect
import numpy as np
input = sys.stdin.readline

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(c) for c in input().split()]
a = sorted(a)
ret = n*(n-1)*(n-2)//6
for i in range(n):
	for j in range(i+1, n):
		low, high = 0, n-1
		pivot = -1
		while (low <= high):
			mid = low + (high - low)//2
			if (a[mid] >= a[i] + a[j]): 
				pivot = mid
				high = mid-1
			else: low = mid+1
		if (pivot != -1): ret -= n-pivot
print(ret)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
m=list(map(int,input().split()))
k=0
m.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        z=m[i]+m[j]
        l=bisect_left(m,z)
        k+=l-j-1
print(k)

Submission status: Accepted

Solution code:
N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        ite_right = bi(L,right)
        count = count + (ite_right - k - 1)

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
l = list(map(int, input().split()))
l.sort()
pattern = 0
for i in range(n - 2):
    a = l[i]
    for j in range(i + 1, n - 1):
        b = l[j]
        c_idx = bisect_left(l, a + b)
        pattern += (c_idx - j - 1)
print(pattern)

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
L.sort()
from bisect import bisect_left
ans = 0
for i1 in range(N-2):
  for i2 in range(i1+1,N-1):
    l1,l2 = L[i1],L[i2]
    #th = bisect_left(L[i2+1:],l1+l2)
    #print(l1,l2,L[i2+1:],(l2-l1+1)*(-1),th)
    th = bisect_left(L,l1+l2)
    ans += max(th-i2-1,0)
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())

num_list = list(map(int,input().split()))
num_list.sort()
res = 0

for a in range(N-2):
    for b in range(a+1,N-1):
        k = bisect.bisect_left(num_list,num_list[a]+num_list[b])
        res += max(k-(b+1),0)
print(res)

Submission status: Accepted

Solution code:
def main():
    import bisect
    n = int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    ans = 0
    for a in range(n):
        for b in range(a+1, n):
            c = bisect.bisect_left(inlis, inlis[a] + inlis[b])
            ans += c - b - 1
    print(ans)     



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
 
input = sys.stdin.readline
 
def main():
    N = int(input())
    L = list(map(int, input().split()))
 
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            # print(a, b)
            c = bisect.bisect_left(L, L[a] + L[b]) - 1
            ans += c - b
 
    print(ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

def is_ok(n, su):
    return l[n] > su

def binary_search(left, right, su):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid, su):  right = mid
        else:  left = mid
    return right

l = sorted(l)
ans = 0
for i in range(2, N):
    for j in range(1, i):
        left = j
        right = -1
        ret = binary_search(right, left, l[i] - l[j])
        if ret != right:  ans += j - ret
print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    l = [int(i) for i in ipt().split()]
    l.sort()
    ans = 0
    dp = [[0]*(2*10**3+1) for i in range(2)]
    for i in l:
        ans += sum(dp[1][i+1::])
        for j in range(i,2*10**3+1):
            dp[1][j] += dp[0][j-i]
        dp[0][i] += 1
    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n=int(input())
l=list(map(int,input().split()))
from bisect import bisect_left
l.sort()

count=0
for a in range(n-2):
    for b in range(a+1,n-1):
        idx=bisect_left(l,l[a]+l[b],lo=b)
        count+=idx-(b+1)

print(count)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

a.sort()
count = 0
for i in range(n-1, 0, -1):
    l = 0
    r = i-1
    while(l<r):
        if a[l] + a[r] > a[i]:
            count += r-l
            r -= 1

        else:
            l += 1

print(count)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
l = sorted(LIST())

ans = 0
for i in range(n-2):
    right = i + 2
    for j in range(i+1, n-1):
        left = j + 1
        while right < n-1 and l[right] < l[i] + l[j]:
            right += 1
        ans += right - left
        if l[right] < l[i] + l[j]:
            ans += 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+2, N):
    a, b = L[i], L[j]
    right = bisect.bisect_right(L, b-a)
    left = max(right, i+1)
    ans += j - left
print(ans)

Submission status: Accepted

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

L.sort(reverse=True)
counter = 0
import bisect

for index1,c in enumerate(L):
    for index2,b in enumerate(L[index1+1:],start=index1+1):
        left = 0 ; right = N
        oppai = c-b
        while left+1<right:
            mid = (left+right)//2
            if L[mid]>oppai:
                left = mid
            else :
                right=mid
        
        index3 = left
        
        if index3>index2:

            counter += index3-index2
print(counter)

Submission status: Accepted

Solution code:
import bisect
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def main2():
    n = int(input())
    l=[int(i) for i in input().split()]
    l.sort(reverse = True)
    res = 0
    for i in range(n-1):
        for j in range(i+1, n-1):
            #index がj以降で　k < c を満たすcで一番小さいc'を探す
            #index(c')-j - 1が三角形の条件を満たす
            nibu = l[j+1:]
            k = max(l[i]-l[j],l[j]-l[i])
            left=bisect_left_reverse(nibu,k)
            res += left
    print(res)

if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

from bisect import bisect_right

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

    L.sort()
    ans = 0
    for b in range(N):
        for a in range(b+1,N):
            upper = b
            lower = bisect_right(L, L[a] - L[b])
            ans += max(0, upper - lower)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    def is_ok(a, key, idx):
        if a[idx] >= key:
            return True
        else:
            return False

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8,i8[:])", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = np.array(input().split(), dtype=np.int64)

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

input = sys.stdin.readline


def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = bisect_left(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


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

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:], i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    def is_ok(a, key, idx):
        if a[idx] >= key:
            return True
        else:
            return False

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8, i8[:])", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = np.array(input().split(), dtype=np.int64)

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("b1(i8[:],i8,i8)", cache=True)
def is_ok(a, key, idx):
    if a[idx] >= key:
        return True
    else:
        return False


@nb.njit("i8(i8[:], i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8, i8[:])", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = np.array(input().split(), dtype=np.int64)

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:], i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] >= key:
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8, i8[:])", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = np.array(input().split(), dtype=np.int64)

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:], i8)")
def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] >= key:
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8, i8[:])")
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = np.array(input().split(), dtype=np.int64)

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    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):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline


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

    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = bisect.bisect_left(L, L[a] + L[b]) - 1
            ans += c - 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):
        a = bisect.bisect(l, l[i]+l[j]-1)
        ans += (a-j-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left,bisect_right

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N, *X = map(int, open(0).read().split())

X.sort()
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k1 = bisect_right(X, X[j] - X[i])
        k2 = bisect_left(X, X[i] + X[j])
        k1 = max(k1, j + 1)
        ans += max(0, k2 - k1)

print(ans)

Submission status: Accepted

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

for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        # j以降の項で、初めてL[k] < a-bとなるkを二分探索する
        if L[-1] > a - b:  # 一番最後の項でもOKな場合(j+1以降全部OK)
            total += N - j - 1
        elif L[j+1] <= a - b:  # 一番最初の項からNGな場合
            continue
        else:
            head = j+1  # head はL[head] > a - bを満たす(OK側)
            tail = N-1  # tail はL[tail] <= a - bを満たす(NG側)
            while head+1 != tail:
                if L[(head + tail)//2] > a - b:  # 中間地点はOK側
                    head = (head + tail) // 2
                else:  # 中間地点はNG側
                    tail = (head + tail) // 2
            total += head - j

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

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]
        c = bisect.bisect_left(l,a+b)
        ans += c - j - 1

print(ans)

Submission status: Accepted

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

n = int(input())
l = list(map(int,input().split()))
l.sort()
mx = l[-1]+l[-2]

length = [0]*(mx+1)
for i in range(n):
    for j in range(i+1,n):
        length[l[i]+l[j]] -= 1
        length[l[j]-l[i]+1] += 1

for i in range(1,mx+1):
    length[i] += length[i-1]

minus = [0]*n
for i in range(n):
    a = i
    for j in range(i+1,n):
        if l[i]*2 - 1 >= l[j]:
            a += 1
    minus[i] = a
#print(length)
#print(minus)
ans = 0
for i in range(n):
    ans += length[l[i]] - minus[i]


print(ans//3)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n = int(input())
    l = sorted(input_list())
    ans = 0
    for a in range(n):
        for b in range(a+1, n):
            ans += bisect.bisect_left(l, l[a]+l[b]) - (b+1)
    print(ans)

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#import math


# input = sys.stdin.readline

def binary_search(arr, key,j):
    ok = j
    ng = len(arr)

    while abs(ok - ng) > 1:
        mid = int((ok + ng) / 2)

        if arr[mid] < key:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    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):
            ok = binary_search(L,L[i]+L[j],j)
            ans += ok-j
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter
N = int(input())
L = list(map(int, input().split()))
L.sort()
m = Counter(L)

ans = 0
for i, x in enumerate(L[:-2]):
    for j, y in enumerate(L[i+1:-1]):
        ans += bisect_left(L, x+y) - (i+j+2)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
from bisect import bisect_left
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]

def main():
    N = ii()
    L = lmi()
    L.sort()
    # print(L)
    # 2辺を固定して、2辺の和より長い辺の数を数える
    count = 0
    for i in range(N):
        for j in range(i+1, N):
            limit = L[i] + L[j]
            longer = bisect_left(L, limit)
            tmp = longer - (j + 1)
            # print(limit, longer, tmp)
            count += longer - (j + 1)

    print(count)
    return

main()

Submission status: Accepted

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

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