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

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

Submission status: Accepted

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

arr.sort()

ans=0

for i in range(N-2):
    for j in range(i+1,N-1):
        k=bisect.bisect_left(arr,arr[i]+arr[j])
        if k>j:
            ans+=k-j-1
        else:
            pass
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        h_min = j
        h_max = N
        while h_max - h_min != 1:
            h_mid = (h_max + h_min) // 2
            if L[i] + L[j] > L[h_mid]:
                h_min = h_mid
            else:
                h_max = h_mid
        cnt += h_min - j
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        s = l[i]+l[j]
        start = j+1
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        ans += end-j-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
ans=0
c=[0]*1001
for i in L:c[i]+=1
for i in range(1000):c[i+1]=c[i]+c[i+1]
for i in range(N-1):
    for j in range(i+1,N):
        l,r=abs(L[i]-L[j]),min(L[i]+L[j]-1,1000)
        ans+=c[r]-c[l]
        if l<L[i] and L[i]<=r:ans-=1
        if l<L[j] and L[j]<=r:ans-=1
print(ans//3)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    l = LI()
    l.sort()
    ans = 0

    for i in range(n):
        for j in range(i):
            mini = l[i] - l[j]
            if mini < l[j]:
                ans += n-bisect.bisect_right(l, mini) - (n-j)

    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 21:39:55 2020

@author: liang
"""

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 20:56:06 2020

@author: liang
"""

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

from bisect import bisect_left

L.sort()
ans = 0
#print(L)
for i in range(N-2):
    #print("1:",i)
    #p = i+2
    #以下O(2N)　定数倍が遅い
    for j in range(i+1,N-1):
        #print("2",i,j)
        t = L[i] + L[j]
        #while p < N and L[p] < L[i] + L[j] :
        #    p += 1
        p = bisect_left(L,t)
            #print("up")
        #print(p)
        #ans += len(L[j+1:p])
        ans += max(0, p - j -1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 20:56:06 2020

@author: liang
"""

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

L.sort()
ans = 0
#print(L)
for i in range(N-2):
    #print("1:",i)
    p = i+2
    #以下O(2?N)　定数倍が遅い
    for j in range(i+1,N-1):
        #print("2",i,j)
        while p < N and L[p] < L[i] + L[j] :
            p += 1
            #print("up")
        #print(p)
        #ans += len(L[j+1:p])
        ans += max(0, p - j - 1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 20:56:06 2020

@author: liang
"""

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

L.sort()
ans = 0
#print(L)
for i in range(N-2):
    #print("1:",i)
    p = i+2
    for j in range(i+1,N-1):
        #print("2",i,j)
        while p < N and L[p] < L[i] + L[j] :
            p += 1
            #print("up")
        #print(p)
        ans += len(L[j+1:p])
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(l,i,j,bisect.bisect_left(l, l[i]+l[j]))
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 sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
    
class SegmentTree():
    
    # 目的関数！！
    def func(self,x,y):
        return x+y
    
    # インデックスは0-start
    # 初期化（配列と初期値）
    def __init__(self, array, initial_value=0):
        
        self.n = len(array)
        self.init_val = initial_value
        self.num = 2**(self.n-1).bit_length()
        self.seg = [self.init_val]*2*self.num
        
        for i in range(self.n):
            self.seg[i+self.num-1] = array[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.func(self.seg[2*i+1],self.seg[2*i+2]) 
    
    # k番目の要素をxに変更
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[2*k+1],self.seg[2*k+2])
    
    # k番目の要素にxを追加
    def add(self,k,x):
        k_tmp = k+self.num-1
        x_tmp = self.seg[k_tmp]+x
        self.update(k,x_tmp)
    
    # [p,q]に対するクエリを処理
    def query(self,p,q):
        q += 1
        if q<=p:
            return self.init_val
        p += self.num-1
        q += self.num-2
        res = self.init_val
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res
    
    # もとの配列を出力
    def result(self):
        return self.seg[self.num-1:self.n+self.num-1]

N,L = ilint()
T = [0]*1001
for i in range(2,N):
    T[L[i]] += 1
tree = SegmentTree(T)
ans = 0
for j in range(1,N-1):
    for i in range(j):
        ans += tree.query(abs(L[j]-L[i])+1,min(L[j]+L[i]-1,1000))
    tree.add(L[j+1],-1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
from itertools import combinations

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for l in combinations(L, 2):
        a = l[0]
        b = l[1]
        x = bisect.bisect_left(L, a + b)
        y = bisect.bisect(L, b - a)
        if b - a < a :
            ans += x - y - 2
        else:
            ans += x - y - 1
    print(ans // 3)


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 - 2):
  for j in range(i + 1, N - 1):
    # L[i] + L[j] より短い棒で且つjより大きいインデックスを数える
    ind = bisect.bisect_left(L, L[i] + L[j])
    num = ind - (j + 1)
    ans += max(num, 0)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect

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

l.sort()
ans=0

for lst in itertools.combinations(range(n-1),2):
  a=l[lst[0]]
  b=l[lst[1]]
  ans+=bisect.bisect_left(l,a+b)-(lst[1]+1)


print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    """
    lo=0
    hi=N
    x=a+b
    while lo<hi:
      mid=(lo+hi)//2
      if L[mid]<x: lo=mid+1
      else: hi=mid
    ans+=lo-(j+1) 
    """
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

Submission status: Accepted

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


def is_ok(i, x):
    return L[i] > x


def bisect(ng, ok, x):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, x):
            ok = mid
        else:
            ng = mid
    return ok


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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
L.sort()
def find(arr, x):
  if arr[0] >= x:
    return 0
  if arr[-1] < x:
    return len(arr)
  
  l = 0
  h = len(arr)
  
  while h - l > 1:
    m = (l+h) // 2
    if arr[m] < x:
      l = m
    else:
      h = m
  return h

ans = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    x = L[i] + L[j]
    temp = find(L[j+1:], x)
    ans += temp
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
sort_L=sorted(L,reverse=True)
ans=0
for n in range(N-2):
    for o in range(n+1,N-1):
        lar=sort_L[n]
        kouho=sort_L[o+1:]
        mid=sort_L[o]
        sa=lar-mid
        left=0
        right=N-o-2
        if kouho[-1]>sa:
            ans+=right+1
        else:
            while right > left + 1:
                half = (right + left) // 2
                if kouho[half] <= sa:
                    right = half
                else:
                    left = half
            if kouho[right]<=sa and kouho[left]<=sa:
                continue
            elif kouho[right]>sa:
                ans+=right+1
            else:
                ans+=left+1
print(ans)

Submission status: Accepted

Solution code:
import math

def canMakeTriangle(a, b, c):
    return abs(b - c) < a

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

res = 0
for i in range(1, N):
    for j in range(i + 1, N):
        a = 0
        b = i
        c = 0
        while b - a >= 1:
            c = (a + b) / 2
            if canMakeTriangle(L[math.floor(c)], L[i], L[j]):
                b = c
            else:
                a = c

        c = math.floor(c)

        if canMakeTriangle(L[c], L[i], L[j]):
            res += i - c
        else:
            res += i - c - 1

print(res)

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

print(ans)

Submission status: Accepted

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

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

def main():
    import bisect
    
    mod=10**9+7
    N=I()
    L=LI()
    L.sort()
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            a=L[i]
            b=L[j]
            ab=a+b
            num=bisect.bisect_left(L,ab)
            
            # print(i,j,num-j)
            ans+=num-j-1
            
                
    print(ans)
    

main()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    import bisect
    n = i_input()
    l = sorted(i_list())
    ans = 0
    for a in range(n-2):
        for b in range(a+1,n-1):
            ans += bisect.bisect(l, l[a]+l[b]-1) -b-1
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

def findnumberofTriangles(arr): 
	n = len(arr) 
	arr.sort() 
	count = 0
	for i in range(0, n-2):  
		k = i + 2 
		for j in range(i + 1, n):  
			while (k < n and arr[i] + arr[j] > arr[k]): 
				k += 1
			if(k>j): 
				count += k - j - 1

	return count 

n = int(input())
arr=[int(x) for x in input().split()]
print(findnumberofTriangles(arr))

Submission status: Accepted

Solution code:
import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

n  = int(input())
bo = list(map(int,input().split()))
 
cnt = 0
bo.sort()
 
for a in range(n-1):
    for b in range(a+1,n):
        cnt += bisect.bisect_left(bo, bo[a]+bo[b]) - (b+1)

print(cnt)

Submission status: Accepted

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

l.sort()
ans=0

for i in range(len(l)-2):
    for j in range(i+2,len(l)):
        a=l[i]
        c=l[j]
        b_min=i+1
        b_max=j-1
        while b_max-b_min>1:
            if l[(b_max+b_min)//2]>c-a:
                b_max=(b_max+b_min)//2
            else:
                b_min=(b_max+b_min)//2
        if l[b_min]>c-a:ans+=j-b_min
        elif l[b_max]>c-a:ans+=j-b_max
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
num=[0]*(max(l)+2)
for i in range(n):
    num[l[i]]=i
for i in range(1,len(num)):
    if num[i]==0:
        num[i]=num[i-1]
ans=0
num3=l[n-1]
for i in range(n-2):
    for j in range(i+1,n-1):
        ans+=max(0,num[min(num3,l[i]+l[j]-1)]-j)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = 0
c = n - 1
for a in range(n - 2):
    c = n - 1
    for b in range(a + 1, n - 1):
        #　各a,bに対してのcを尺取法で探索
        while l[a] >= l[b] + l[c]:
            c -= 1
            if c <= b:
                break
        else:
            # print(l[a], l[b], l[c])
            ans += c - b
            continue
        break
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(1,n):
    for j in range(i+1,n):
        tmp = L[:i]
        v = L[j]-L[i]
        idv = bisect.bisect_right(tmp,v)
        if idv!=len(tmp):
            ans += len(tmp)-idv
print(ans)

Submission status: Accepted

Solution code:
def is_ok(a,b,c):
    return L[a] < L[b] + L[c]
def meguru_bisect(ng, ok, a, b):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, b, mid):
            ok = mid
        else:
            ng = mid
    return ok
N = int(input())
L = sorted(list(map(int, input().split())), reverse=True)
ans = 0
for a in range(N):
    for b in range(a+1, N):
        ans += meguru_bisect(N,b,a,b)-b
print(ans)

Submission status: Accepted

Solution code:
def is_ok1(a,b,c):
    return L[b] < L[c] + L[a]
def is_ok2(a,b,c):
    return L[c] < L[a] + L[b]
def meguru_bisect(ng, ok, is_ok, a, b):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, b, mid):
            ok = mid
        else:
            ng = mid
    return ok
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for a in range(N):
    for b in range(a+1, N):
        ans += max(0, meguru_bisect(N, b, is_ok2, a, b)-meguru_bisect(b, N, is_ok1, a, b)+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):
        c = L[i] + L[j]
        # a+bが入る場所を返す
        idx = bisect_left(L, c)
        ans += max(0, idx - (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):
    a=l[i]+l[j]
    b=l[j]-l[i]
    
    x=bisect.bisect_right(l,b)
    y=bisect.bisect_left(l,a)-1
    X=max(j+1,x)
    if y-X+1>0:
      ans+=y-X+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):
        k = l[i] + l[j]
        pos = bisect_left(l, k)
        ans += max(0, pos - j - 1)
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-2):
  for j in range(i+1, n-1):
    sum = l[i] + l[j]
    index = bisect.bisect_left(l, sum)
    cnt += index - j - 1

print(cnt)

Submission status: Accepted

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

a.sort()
import bisect
ans=0
#A=[1,2,3,4,5] #ソート済み
#index = bisect.bisect_left(A, 3) #2 同じ数字があった場合、前側の挿入箇所が返ってきている
#index = bisect.bisect_right(A, 3) # 3 同じ数字があった場合、後ろ側の挿入箇所が返ってきている
#A.insert(index, 3) #挿入
#print(a)
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        #a[i]<a[j]

        #a[k]<a[i]<a[j]

        #a[k]+a[i]>a[j]
        #=>a[i]> a[k] >a[j]-a[i]

        ll= bisect.bisect_right(a, a[j]-a[i])

        rr= bisect.bisect_left(a, a[i])
        if a[rr+1]==a[i]:
            rr=i
        #print(a[i],a[j],"|",ll,rr,max(0,rr-ll))
        ans+=(max(0,rr-ll))

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):#二番目に短い棒
    #1+2番目の棒の長さより短く、2番目に短い棒より長い棒の範囲を探す
    ans += bisect_left(l,l[i]+l[j])-(j+1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from bisect import bisect_left

    n = int(input())
    l = sorted(map(int, input().split()))
    ld = deque(l)
    cnt = 0
    for a in range(n - 2):
        l_a = ld.popleft()
        for b in range(a + 1, n - 1):
            cnt += bisect_left(l, l_a + l[b]) - b - 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

n = int(input())
l = sorted(map(int, input().split()))
ld = deque(l)
cnt = 0
for a in range(n - 2):
    l_a = ld.popleft()
    for b in range(a + 1, n - 1):
        cnt += bisect_left(l, l_a + l[b]) - b - 1
print(cnt)

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
def isOK(a,b,c):
    return abs(a-b) < c < a+b
a_ls.sort()
ans = 0
for i in range(n):
    short = a_ls[i]
    r = i+1
    num = 0
    for l in range(i+1,n-1):
        while r+1 < n and isOK(short, a_ls[l], a_ls[r+1]):
            r += 1
        num += r - l
        if l == r:
            r += 1
    ans += num
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l_ls = list(map(int, input().split()))
l_ls.sort()
def check(a,b,c):
    return abs(a-b) < c < a+b
ans = 0
for i in range(n):
    short = l_ls[i]
    num = 0
    r = i+1
    for l in range(i+1,n):
        while r+1 < n and check(short, l_ls[l], l_ls[r+1]):
            r += 1
        num += r - l
        if r == l:
            r += 1
    ans += num
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
#print(a)
ans=0
for i in range(n-1,1,-1):
    for j in range(i-1,0,-1):
        t=bisect.bisect_right(a,a[i]-a[j])
        #print(a[i],a[j],a[i]-a[j],t,j-t)
        if j-t>0:
            ans+=j-t
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):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    L=list(mi())

    ans = 0
    L.sort()
    for ai in range(N):
        for bi in range(ai+1,N):
            a,b = L[ai],L[bi]

            left = bisect.bisect_left(L,abs(a-b)+1)
            right = bisect.bisect_right(L,a+b-1)

            count = right - left

            if left <= ai <= right:
                count -= 1

            if left <= bi <= right:
                count -= 1
            
            ans += count
            # if count > 0:
            #     print(a,b,count) 
            

    print(ans//3)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

print(ans)

Submission status: Accepted

Solution code:
import bisect


def main():
    n = int(input())
    l = sorted(list(int(i) for i in input().split()))

    cnt = 0

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

    print(cnt)


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

Submission status: Accepted

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

import bisect

def main():
  N = int(input())
  L = list(sorted(map(int,input().split())))
  res = 0
  for i in range(N-2):
    x = L[i]
    for j in range(i+1,N-1):
      y = L[j]
      res += bisect.bisect_left(L,x+y) - j - 1


  print(res)
  return

main()

Submission status: Accepted

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

cnt = 0

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

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

Submission status: Accepted

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

l.sort(reverse=True)
ans=0

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

Submission status: Accepted

Solution code:
#それゆけにぶたんまん
#python3.8.2のTLEの壁に阻まれました←ぱいぱいまんに助けてもらった
#てかライブラリ使えばよくねver
from bisect import bisect_left
n = int(input())
l = sorted(list(map(int,input().split())))

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

print(ans)

Submission status: Accepted

Solution code:
#それゆけにぶたんまん
#python3.8.2のTLEの壁に阻まれました
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        #jより大きい整数kでl[k]<l[i]+l[j]を満たす最大のk
        le = j
        ri = n
        while ri-le>1:
            m = (ri+le)//2
            if l[m]<l[i]+l[j]:
                le = m
            else:
                ri = m
        ans += le-j

print(ans)

Submission status: Accepted

Solution code:
# 小さいのを2つ選んで最後の1つをにぶたん
# なぜかTLEなる
from bisect import bisect_left
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        # ok, ng = j, n
        # while (ng - ok) > 1:
        #     mid = (ng + ok) // 2
        #     if l[i] + l[j] > l[mid]:
        #         ok = mid
        #     else:
        #         ng = mid
        # ans += ok - j
        # ↑とやってることは同じはずなんだけどなぜかTLEなるので組み込みのやつを使ってみる
        a = bisect_left(l, l[i] + l[j])
        ans += a - 1 - j
print(ans)

Submission status: Accepted

Solution code:
def biserch(n,List):
    left = 0
    right = len(List)
    while left < right:
        mid = (left+right)//2
        if n <= List[mid]:
            right = mid
        else:
            left = mid + 1
    
    return 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):
        key = L[i] + L[j]
        anchor = biserch(key,L)
        
        ans += max(anchor - (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 a in range(0, n-2):
    for b in range(a+1, n-1):
        c = l[a] + l[b]
        ans += bisect.bisect_left(l, c) - b - 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect

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

#n=7
#l=[218, 233, 389, 645, 704, 728, 786]

#print(l)
icnt=0
for a in range(n-2):
    for b in range(a+1,n-1):
        nc=bisect(l,l[a]+l[b]-1)
        if nc>b+1:
            icnt+=nc-(b+1)
#            print(a,b,nc,l[a],l[b],l[a]+l[b])
        
print(icnt)