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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


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


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, L):
    L.sort()
    ans = 0
    for i, a in enumerate(L):
        for j in range(i+1, N):
            b = L[j]
            l = max(a-b, b-a)
            r = a+b
            x = bisect.bisect_left(L, l, lo=j+1)
            y = bisect.bisect_left(L, r, lo=j+1)
            ans += y - x
            if x <= j <= y:
                ans -= 1
            if x <= i <= y:
                ans -= 1

    return ans


def main():
    N = read_int()
    L = read_int_n()
    print(slv(N, L))

    # N = 2 * (10**3)
    # L = [random.randint(1, 1000) for _ in range(N)]
    # print(slv(N, L))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for ia, a in enumerate(L):
    for ib, b in enumerate(L[ia+1:], ia):
        ans += bisect_left(L, a+b) - ib - 2

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
import bisect
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
l = inl()
acc = 0
l.sort()
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    e = bisect.bisect_left(l[j+1:],a+b)
    #ddprint("a {} b {} i {} j {} e {}".format(a,b,i,j,e))
    acc += e  #-j-1
print(acc)

Submission status: Accepted

Solution code:
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
from bisect import insort
from bisect import insort_right
from bisect import insort_left

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

cnt = 0
for i in range(N):
  for j in range(i+1, N):
    s = L[i] + L[j]
    x = bisect_left(L, s)
    #print((L[i], L[j]), s, x)
    cnt += max(x - j - 1, 0)
print(cnt)

Submission status: Accepted

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

lst.sort()

for i in range(n):
    for j in range(i+1,n):
        b,c = lst[i],lst[j]
        posr = bisect_left(lst,b+c)
        posl = max(j+1,bisect_left(lst,abs(b-c)))
        ans += (posr - posl)
print(ans)

Submission status: Accepted

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

L.sort()
'''
print(L)
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[i] + L[k] and L[k] < L[i] + L[j]:
                print(i,j,k)
                '''
ans = 0

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


print(ans)

Submission status: Accepted

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

memo = [0]*1001
for x in range(1001):
    for i in arr:
        if i < x:
            memo[x] += 1

result = 0
for a in range(N):
    for b in range(a+1, N):
        aa = arr[a]
        bb = arr[b]
        if aa+bb > 1000:
            result += N-b-1
        else:
            result += memo[aa+bb]-b-1

print(result)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
bar = [ int(v) for v in input().split() ]
bar.sort()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect.bisect_right(bar,bar[i]+bar[j]-1) - j - 1
print(ans)

Submission status: Accepted

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

from bisect import bisect_left
def get_number_triangle(i, j, L):
    two_sum = L[i]+L[j]
    idx = bisect_left(L, two_sum)
    return idx - j - 1

ret = 0
for i in range(N):
    for j in range(i+1, N):
        ret += get_number_triangle(i, j, L)
print(ret)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left, bisect_right
n = getN()

nums = getList()
nums.sort()

ans = 0
for i, num1 in enumerate(nums):
    for j , num2 in enumerate(nums[i+1:]):
        tmp = num1 + num2
        idx_min = bisect_left(nums, tmp)
        idx_max = bisect_right(nums, num2 - num1)
        # print(num1, num2, idx_min - idx_max)
        ans += idx_min - idx_max - 2
        if num2 >= num1 * 2:
            ans += 1
# print("=======")
# anss = 0
# for i, n1 in enumerate(nums):
#     for j, n2 in enumerate(nums):
#         for k, n3 in enumerate(nums):
#             if i != j and j != k and k != i:
#                 if n1 < n2 + n3 and n2 < n1 + n3 and n3 < n1 + n2:
#                     print(n1, n2, n3)
#                     anss += 1

print(ans// 3)
# print(anss/6)

"""
1 2 1  0
1 3 1  0
1 4 1  0
1 5 1  0
2 3 3  234 - 23 > 1 234
2 4 3  345 - 4 > 234, 245 
2 5 2  45 - 5 > 245
3 4 4  2345 - 34 > 234, 345
3 5 3  345 - 35 > 345 
4 5 4  2345 - 45 > 245, 345 
"""

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

dp = defaultdict(lambda x:-1)

def main():
	n = int(input())
	l = list(map(int,input().split()))
	l.sort()
	ans = 0
	for mx in reversed(range(1,n)):
		for sc in reversed(range(1,mx)):
			tr_mx = l[mx] - l[sc] + 1
			tr = bisect.bisect_left(l,tr_mx)
			if(sc - tr > 0):
				ans += sc-tr
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
Ls = list(map(int, input().strip().split()))

Ls.sort()

total = 0
#print(Ls)
for i in range(N):
	a = Ls[i]
	for j in range(i + 1, N):
		b = Ls[j]
		c_min = b - a + 1
		c_max = a + b - 1
		l = bisect.bisect_left(Ls, c_min, lo = j + 1)
		if l != N:
			r = bisect.bisect_right(Ls, c_max, lo = j + 1)
			if r:
				r = r - 1
				if r >= l:
					total += r - l + 1
#					print(a, b, c_min, c_max, l, r)
print(total)

Submission status: Accepted

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

print(ret)

Submission status: Accepted

Solution code:
import bisect

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


ans = 0

l.sort()
# print(l)
for x in range(n):
    for y in range(x+1, n):
        t = bisect.bisect_left(l, max(l[x] - l[y], l[y] - l[x])+1, y+1)
        #print(l[x], l[y], max(l[x] - l[y], l[y] - l[x]), t, l[t])
        t2 = bisect.bisect_left(l, l[x] + l[y], y+1)
        #print(t2, l[t2] if t2 < n else None)
        #print(t2 - t)
        t3 = t2 - t
        if t3 > 0:
            ans += t3
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import bisect


#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	L = getlist()
	L = sorted(L)
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			x = L[i] + L[j]
			ans += bisect.bisect_left(L, x) - j - 1
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for k in range(N-2):
    for l in range(N-k-2):
#        print(k,l,bisect.bisect_left(L,L[-l-1]-L[k]+1))
        ans += min(N-k-l-2,N-bisect.bisect_left(L,L[-l-1]-L[k]+1)-l-1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
R = sorted(L)
ans = 0
diff = [L[i] - L[i+1] for i in range(N-1)]

for i in range(N):
    d = 0
    for j in range(i+1, N):
        d += diff[j-1]
        k = bisect.bisect_left(R, d+1)
        ans += max(N-k-1 - j, 0)

print(ans)

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


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

L.sort()

Ns = [0] * (2*10**3 + 10)

for l in L:
    Ns[l] += 1

cNs = [0] * len(Ns)
for i in range(1, len(Ns)):
    cNs[i] = cNs[i - 1] + Ns[i]

count = 0
for i in range(N - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        toosmall = cNs[L[i] - L[j]]
        count += max(0, j - toosmall)

        

print(count)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
from bisect import bisect_right as br
input = sys.stdin.buffer.readline
N = int(input())
L = list(map(int, input().split()))
L.sort()
dl = []
res = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    d0 = L[i] + L[j]
    d1 = i
    d2 = j
    d3 = abs(L[i] - L[j])
    ind = bl(L, d0)
    ind2 = br(L, d3)
    res += ind - ind2
    if ind2 <= d1 <= ind:
      res -= 1
    if ind2 <= d2 <= ind:
      res -= 1
  #print(res, d, ind, ind2)
print(res // 3)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = list(map(int, input().split()))
index = [-1 for i in range(2001)]
L.sort()

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

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

Submission status: Accepted

Solution code:
def check(a, b, c):
    return True if c < a + b else False

import bisect
def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    targets.sort()
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1, len(targets)):
            rest = targets[j+1:len(targets)]
            ans += bisect.bisect_left(rest,targets[i]+targets[j])

    print(ans)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
Ls = sorted(list(map(int, input().split())),reverse=True) #ソートしておく
r = list(reversed(Ls))
from bisect import bisect_right
ans = 0
for i in range(N):
    for j in range(i+1,N):
        x = Ls[i] - Ls[j]
        ind = bisect_right(r,x)
        ans += max(0,N-ind-j-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import bisect

L.sort()
L.append(1001)

ans = 0
for i in range(N - 2):
    for k in range(i + 2, N):
        # if a >= c - a: continue
        j_left = bisect.bisect_right(L, L[k] - L[i])
        if j_left <= i: j_left = i + 1
        if j_left >= k: continue
        #
        if L[j_left] == L[k] - L[i]:
            j_left += 1
        #
        j_right = bisect.bisect_left(L, L[k] + L[i])
        if j_right < 0: continue
        if j_right >= k: j_right = k - 1
        #
        if L[j_right] == L[k] + L[i]:
            j_right -= 1
        #
        # print("#", i, (j_left, j_right), k, '->', (L[j_left], L[j_right]), max(0, j_right - j_left + 1))
        ans += max(0, j_right - j_left + 1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import bisect
ans = 0
for i, a in enumerate(Ls[:-2]):
  for j, b in enumerate(Ls[i + 1:-1], start=i + 1):

    rest = a + b
    end_idx = bisect.bisect_left(Ls, rest)

    start_idx = j + 1
    ans += end_idx - start_idx

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(n-1, 1, -1):
    for b in range(a-1, 0, -1):
        length1 = L[a]
        length2 = L[b]
        limit = length1 - length2 + 1
        index = bisect.bisect_left(L, limit)
        ans += max(0, b - index)

print(ans)

Submission status: Accepted

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

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

l.sort()
ans = 0

for i in range(n):
    count = i
    for j in range(i+1,n-1):
        ad = l[i] + l[j]
        if count < n:
            while l[count] < ad and count < n:
                count += 1
                if count == n:
                    break
        ans += count - j - 1

print(ans)

Submission status: Accepted

Solution code:
def CountTriangles( A):
	n = len(A);
	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);

n = int(input())
a = [ int(i) for i in input().split() ]
CountTriangles(a);

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  l = list(int(i) for i in input().split())
  l = sorted(l)
  ans = 0
  #print(l)
  for i in range(n):
    for j in range(i+1,n):
        a = l[i]
        b = l[j]
        c_max = bisect.bisect_left(l,a+b)
        if c_max <= j+1:
          continue
        else:
          ans += c_max-j-1
          #print(c_max-2)
        #print(c_max,i,j)

  print(ans)
  
solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
ls = sorted(list(map(int, input().split())))
total = 0
for i in range(n):
    for j in range(i+1, n):
        b, c = ls[i], ls[j]
        lower = abs(b-c) + 0.5
        upper = b+c - 0.5
        ii = bisect_left(ls, lower)
        jj = bisect_left(ls, upper)
        cnt = jj - ii
        if ii <= i < jj:
            cnt -= 1
        if ii <= j < jj:
            cnt -= 1
        total += cnt
total //= 3

print(total)

Submission status: Accepted

Solution code:
import bisect

def solve(n, l):
    l.sort()
    r = 0
    for i in range(n - 2):
        li = l[i]
        for j in range(i + 1, n - 1):
            r += bisect.bisect_left(l, li + l[j], j + 1) - j - 1
    return r

def main():
    n = int(input())
    l = [int(x) for x in input().split()]
    print(solve(n, l))


main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
n=int(input())
s=sorted(list(map(int,input().split())))
q=0
d=[[""]*(1001)for i in range(1001)]
for i in range(n):
    for j in range(i+1,n):
        x,y=max(s[i],s[j]),min(s[i],s[j])
        if d[x][y]=="":
            c=br(s,x+y-1)-bl(s,x-y+1)-1
            if x-y<y:
                c-=1
            c=max(c,0)
            d[x][y]=c
        q+=d[x][y]
print(q//3)

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
#print(L)

for i in reversed(range(2, N)):
    for j in reversed(range(1, i)):
        idx = bisect_right(L, L[i] - L[j])
        #print(i, j, idx)
        if idx < j:
            ans += j - idx

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N = ii()
    L = lmis()
    L.sort()
    import bisect
    ans = 0
    for ia in range(N):
        a = L[ia]
        for ib in range(ia+1, N):
            b = L[ib]
            ans += max(0, bisect.bisect_left(L, a+b) - (ib+1))
    print(ans)

main()

Submission status: Accepted

Solution code:
def fnt(arr,n): 
  
     
     
     
    count = 0
  
     
    for i in range(0,n-2): 
  
         
        k = i + 2
  
        # Fix the second element 
        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=input()
arr=arr.split()
arr=list(map(int,arr))
arr.sort()
print(fnt(arr,n))

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
cnt = [0 for i in range(1001)]
for l in L:
	cnt[l] += 1
total = [0 for i in range(1001)]
for i in range(1, 1001):
	total[i] = total[i-1] + cnt[i]

ans = 0
for i in range(1, 1001):
	if cnt[i] <= 0:
		continue
	I = cnt[i]
	for j in range(i, 1001):
		J = cnt[j]
		if J <= 0:
			continue
		if i == j and J <= 1:
			continue
		base = (I * (I - 1)) // 2 if i == j else I * J
		M = min(1000, i + j - 1)
		if i == j:
			if cnt[j] >= 3:
				ans += (I * (I-1) * (I-2)) // 6
		elif cnt[j] >= 2:
			ans += I * (J * (J-1)) // 2
		ans += base * (total[M] - total[j])
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
sys.setrecursionlimit(10**7)
N = int(input())
L = list(map(int, input().split()))
L.sort()

cnt = 0
lenL = len(L)
for i, l1 in enumerate(L):
    for j, l2 in enumerate(L[i+1:]):
        sumll = l1 + l2
        pos = bisect.bisect_left(L, sumll)
        add = pos - i - j - 2
        cnt += add
print(cnt)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
l = [int(x) for x in input().split()]

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

Submission status: Accepted

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ll=[0]*(l[-1]+1)

for i in l:
    ll[i]+=1
for i in range(1,len(ll)):
    ll[i]+=ll[i-1]

ans=0
import itertools
for i,j in itertools.combinations(l,2):
    if max(i-j,j-i)<i+j-1:
        ans+=ll[min(len(ll)-1,i+j-1)]-ll[min(len(ll)-1,max(i-j,j-i))]
        if max(i-j,j-i)<i<i+j:
            ans-=1
        if max(i-j,j-i)<j<i+j:
            ans-=1
print(ans//3)

Submission status: Accepted

Solution code:
import bisect as bi

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

ans=0

for i in reversed(range(2,N)):
    a=L[i]
    for j in reversed(range(1,i)):
        b=L[j]
        ans+=j-bi.bisect_left(L[:j],a-b+1)

print(ans)

Submission status: Accepted

Solution code:

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

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

num_length = [0]*(2001)

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

for i in range(1, len(num_length)):
	num_length[i] += num_length[i - 1]

sum = 0
for i in range(N):
	for j in range(N):
		if i != j:
			x = max(L[i], L[j]) - min(L[i], L[j])
			sum += num_length[L[i] + L[j] - 1]
			sum -= num_length[x]
			if L[i] > x:
				sum -= 1
			if L[j] > x:
				sum -= 1


print(sum//6)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N = II()
    l_list = LI()

    # 短い順
    l_list = sorted(l_list)
    ind_list = list(range(len(l_list)))

    from bisect import bisect_left, bisect_right
    from itertools import combinations
    dprint(l_list)
    cnt = 0
    for a, b in combinations(ind_list, 2):
        # 2つえらぶ

        # 残りでできたl_listを作る
        # cand_list = []
        # for c in range(len(l_list)):
        #     if c != a and c!= b:
        #         cand_list.append(l_list[c])

        # cのmax, min
        la = l_list[a]
        lb = l_list[b]

        mx = la + lb
        mn = max(la, lb) - min(la, lb)

        # cand_listをbisectする
        right_ind_plus1 = bisect_left(l_list, mx)
        left_ind = bisect_right(l_list, mn)

        # dprint(la, lb, mn, mx, l_list, left_ind, right_ind_plus1, cnt)

        cnt += right_ind_plus1 - left_ind

        if left_ind <= a and a < right_ind_plus1:
            cnt -= 1

        if left_ind <= b and b < right_ind_plus1:
            cnt -= 1

    print(cnt//3)

solve()

Submission status: Accepted

Solution code:
N=int(input())
L = [int(i) for i in input().split()]
L.sort(reverse=True)
ans = 0
for a_index,a in enumerate(L):
    if a_index == N-1:break
    for b_index in range(a_index+1,N):
        b = L[b_index]
        min_c = a - b #min_cより大きい
        U = N #つねにmin_c以下
        D = -1 #つねにmin_cより大きい
        if b<=min_c:continue
        while U-D > 1:
            X = (U+D)//2
            if L[X]<=min_c:
                U = X
            else:
                D = X
        c_index_max = D
        ans += c_index_max - b_index
print(ans)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

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:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


solve2()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect


def main():
  input()
  values = list(map(int, input().split()))
  values.sort()
  result = 0

  for i in range(len(values) - 2):
    for j in range(i + 1, len(values) - 1):
      targets = values[j + 1:]
      index = bisect.bisect_left(targets, values[i] + values[j])
      result += index

  print(result)


if __name__ == '__main__':
  main()

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

Submission status: Accepted

Solution code:
import bisect
def main():
    N = int(input())
    L = [int(n) for n in input().split()]
    # L = list(range(int(2 * 1e3)))
    L.sort()
    res = 0
    for i in range(N):
        for j in range(i+1, N):
            c = L[i]
            b = L[j]
            targ = b - c
            #targ <
            insert_index = bisect.bisect_right(L, targ)
            if insert_index >= i:
                continue
            # print(b, c)
            # print(insert_index)
            # print("---")
            res += i - insert_index
    print(res)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A,B = [int(a) for a in input().split()]
    L = sorted([int(a) for a in input().split()])
    # xy = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]

    r = 0
    for a in range(N):
        for b in range(a + 1, N):
            p = bisect.bisect_left(L, L[a] + L[b])
            r += (p - 1 - b)

            # for c in range(N-1,b,-1):
            #     if L[a] + L[b] > L[c]:
            #         r += (c-b)
            #         break

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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]
        k = bisect.bisect_left(Ls, A + B, j + 1)
        S += k - j - 1
print(S)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bi
n=int(input())
l=sorted(map(int,input().split()))
ans=0
#print(l)
for i in range(n):
    for j in range(i+1,n):
        ans+=bi(l,l[i]+l[j])-j-1
#        print(i,j,bi(l,l[i]+l[j]),ans)
print(ans)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
llist = list(int(i) for i in input().split())
llist=sorted(llist)
kotae=0
#print(llist)
swit=0
etswit=0

for i in range(n-2):
    swit=0
    for j in range(n-2-i):
        a=i
        b=i+j+1
        koho=llist[b+1:]
        nagasa=len(koho)
        if etswit==0:
            if swit==0:
                index = bisect.bisect_left(koho, llist[a]+llist[b])
                if index==nagasa:
                    swit=1
                    if j==0:
                        etswit=1
                #print(a,b,koho,index)
                kotae+=index
            else:
                kotae+=nagasa
        else:
            kotae+=nagasa

print(kotae)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
import bisect
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    L = LMIIS()
    L.sort()
    count = 0
    for i in range(N):
        for j in range(i+1,N):
            a = L[i]
            b = L[j]
            l = bisect.bisect_right(L,a-b,lo=j+1)
            r = bisect.bisect_left(L,a+b,lo=j+1)
            count += max(r - l ,0)
    print(count)



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

Submission status: Accepted

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