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:
import sys
from itertools import combinations
import bisect


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    ans = 0
    for i, j in combinations(l, 2):
        lb = abs(j - i)
        ub = i + j
        ans += bisect.bisect_left(l, ub) - bisect.bisect_right(l, lb)
        for e in (i, j):
            if e > lb:
                ans -= 1

    print(ans // 3)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))

Submission status: Accepted

Solution code:
from bisect import bisect


from bisect import bisect_left

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

lis.sort()

cnt = 0
for i in range(n-2):
    a = lis[i]
    for j in range(i+1, n-1):
        b = lis[j]
        tmp = bisect_left(lis, a+b)
        
        cnt += tmp - 1 -j
    

print(cnt)

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"""
    ok = -1
    ng = 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):
            x = binary_search(L, L[a] + L[b])
            ans += (x - 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

input = sys.stdin.readline


@nb.njit("i8(List(i8, reflected=True),i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ok = -1
    ng = 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,List(i8, reflected=True))", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = binary_search(L, L[a] + L[b])
            ans += (x - 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
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 a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = bisect_left(L, L[a] + L[b])
            ans += (x - 1 - b)

    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 a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = bisect_left(L, L[a] + L[b], lo=b)
            ans += (x - 1 - b)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

def solve():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            k = bisect.bisect_left(l, l[i]+l[j])
            res += max(k-(j+1), 0)
    print(res)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

L.sort()
c=0
for i in range(n-2):
    ci=L[i]
    for j in range(i+1,n-1):
        cij = ci+L[j]
        c += bisect.bisect_left(L,cij,j+1,n)-j-1

print(c)

Submission status: Accepted

Solution code:
import bisect

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

for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect.bisect_left(l, l[i]+l[j])
        if c_i > j:
            ans += c_i - j - 1
        else:
            continue
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

count = 0
for i in range(n):
    for j in range(i + 1, n):
        l = bisect_right(stick, stick[j] - stick[i])
        r = bisect_left(stick, stick[i] + stick[j]) # [l, r) が範囲
        if j + 1 >= r:
            continue
        count += r - max(l, j + 1)
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

count = 0
for i in range(n - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        l = bisect_right(stick, stick[i] - stick[j])
        r = bisect_left(stick, stick[i] + stick[j]) # [l, r) が範囲
        if j <= l:
            break
        count += min(r, j) - l
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

count = 0
for i in range(n - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        l = bisect_left(stick, stick[i] - stick[j] + 1)
        r = bisect_right(stick, stick[i] + stick[j] - 1) - 1
        if j <= l or l > r:
            break
        count += min(r + 1, j) - l
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

count = 0
for i in range(n):
    for j in range(i + 1, n):
        l = bisect_left(stick, stick[j] - stick[i] + 1)
        r = bisect_right(stick, stick[i] + stick[j] - 1) - 1
        if r < 0 or l >= n:
            break
        count += r - l + 1
        if l <= i <= r:
            count -= 1
        if l <= j <= r:
            count -= 1
print(count // 3)

Submission status: Accepted

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

s = 0

l.sort()

for i in range(n-2):
    j = n-2
    k = n-1
    while i < j:
        if l[k] >= l[i] + l[j] and j < k:
            #print(0, i, j, k)
            k -= 1
        else:
            #print(1, i, j, k)
            s += k - j
            j -= 1


print(s)

Submission status: Accepted

Solution code:
import bisect
import collections
N=int(input())
L=list(map(int,input().split()))
L.sort()
c = collections.Counter(L)
#print(L)
 
#b-a < c < a+b

#a<=b<=c
ans=0
L_a=L[:N-2]
for i,a in enumerate(L_a):
    L_b=L[i+1:N-1]
    for j,b in enumerate(L_b,start=i+1):
        x=bisect.bisect(L[j+1:],a+b)
        ans+=x
        if a+b==L[j+x]:
            #print(a,b,L[j+x])
            ans-=c[a+b]
        #print(i,a,j,b,x,N-j-1,L[j+1:])
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

# print(L)

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

Submission status: Accepted

Solution code:
N=int(input())
L= list(map(int,input().split()))
L_sorted=sorted(L,reverse=False)#昇順
count=0
import bisect
for i in range(N):
    for j in range(i+1,N):
        a=L_sorted[i]
        b=L_sorted[j]        
        bisect.bisect_left(L_sorted,a+b)
        count+=bisect.bisect_left(L_sorted,a+b)-j-1
print(count)

Submission status: Accepted

Solution code:
import bisect

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

L_sorted = sorted(L, reverse = False)#昇順

count = 0
for i in range(N):#aの選び方
    for j in range(i+1,N):#bの選び方
        a = L_sorted[i]
        b = L_sorted[j]#b <= c < a+b
        count += bisect.bisect_left(L_sorted, a+b) - j -1
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = sorted(map(int, input().split()))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        r = bisect_left(A, A[i]+A[j])
        ans += r-(j+1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

    print(ans)

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
for ai in range(n):
  for bi in range(ai+1,n):
    ok,ng = bi,n
    while ng-ok>1:
      mid = (ng+ok)//2
      if l[mid]<l[ai]+l[bi]:
        ok = mid
      else:
        ng = mid
    ans += ok-bi
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l_ls = list(map(int, input().split()))
l_ls.sort()
stick_count = [0] * (10**3+1)
stick_csum = [0] * (10**3+1)
for i in range(n):
    stick_count[l_ls[i]] += 1
now = 0
for i in range(10**3+1):
    now += stick_count[i]
    stick_csum[i] = now

ans = 0
for first_i in range(n):
    for second_i in range(first_i+1, n):
        #境界は含まない
        greater_than = abs(l_ls[first_i] - l_ls[second_i])
        smaller_than = min(10**3+1,l_ls[first_i] + l_ls[second_i])
        num_canmake = max(0, stick_csum[smaller_than-1] - stick_csum[greater_than])
        if greater_than < l_ls[first_i] < smaller_than:
            num_canmake -= 1
        if greater_than < l_ls[second_i] < smaller_than:
            num_canmake -= 1
        num_canmake = max(0,num_canmake)
        ans += num_canmake
print(ans//3)

Submission status: Accepted

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

def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    judge = L[i] < L[j] + L[arg]
#    print(judge, i, j, arg, L[i], L[j], L[arg])
    return judge

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

count = 0
for i in range(n):
    for j in range(i+1, n):
        k = meguru_bisect(n+1, j)
        if k > j:
            #print(i, j, k, L[i], L[j], L[k])
            count += k - j
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Binary_Search_Small_Count(A,x,sort=True,equal=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()
        
    N=len(A)
    if A[-1]<x:
        return N
    elif x<A[0] or (not equal and x==A[0]):
        return 0

    L,R=0,N
    while R-L>1:
        C=L+(R-L)//2
        if x<A[C] or (not equal and x==A[C]):
            R=C
        else:
            L=C
    return R
#=======================================
N=int(input())
L=list(map(lambda x:int(x),input().split()))
inf=float("inf")

T={}
for i in range(N):
    x=L[i]
    if x in T:
        T[x]+=1
    else:
        T[x]=0
        
    L[i]=(x,T[L[i]])
L.sort()

D=0
for i in range(N):
    (b,y)=L[i]
    for j in range(i+1,N):
        (c,z)=L[j]

        X=Binary_Search_Small_Count(L,(b,y),False,False)
        Y=Binary_Search_Small_Count(L,(c-b,inf),False,True)

        D+=max(0,X-Y)
print(D)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

from bisect import bisect_left

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

X.sort()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        k = bisect_left(X, X[i] + X[j])
        ans += k - j - 1

print(ans)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
p = 0
def is_ok(arg,l):
    return ls[arg] < l
def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        l = ls[i] + ls[j]
        if is_ok(mid,l):
            ok = mid
        else:
            ng = mid
    return ok
for i in range(n-2):
    for j in range(i+1,n-1):
        ng = n
        ok = j
        m = meguru_bisect(ng, ok)
        p += m-j 
print(p)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

# a<b<c として、aとbを固定する
# 残る条件は c<a+b のみ
# aとbの固定方法がO(N^2), cの二分探索がO(logN)、結局O(N^2logN)
# 二分探索は事前にソートが必要

# ex. 2, 4(a), 4, 7(b), | 8, 9, 9 | (ここにa+b=11が挿入される), 12, 14
# cとして適切なのは8,9,9の3通り
# bisect_rightだとa+bが存在した時にバグる

for ai in range(n):
    for bi in range(ai + 1, n):
        ans += bisect_left(l, l[ai] + l[bi]) - bi - 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from bisect import *
def max2(x,y):
    return x if x > y else y
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i, j in combinations(range(N), 2):
    a, b = L[i], L[j]
    res += max2(bisect_left(L, a+b) -1 - j, 0)
print(res)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
import bisect
#####################################
n=int(input())
A=INPUT()
A.sort()
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(A,A[i]+A[j],0,n)-1-j
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for i in range(n):
    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
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
def sub(x):
    j = n-1
    ans = 0
    for i in range(x+1, n-1):
        if j<=i:
            break
        while j-1>i and l[i]+l[j]<=l[x]:
            j -= 1
        if i<j and l[i]+l[j]>l[x]:
            ans += (j-i)
#         print(i,j)
    return ans
ans = 0
for x in range(n-2):
    ans += sub(x)
#     print(ans)
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-1):
    for k in range(i+1,N-1):
        a=L[i]+L[k]
        b=bisect.bisect_left(L,a)
        ans=ans+(b-k-1)

print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    L = sorted(map(int, input().split()))
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect_right(L, L[a] + L[b] - 1) - b - 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
#二分探索をするライブラリ

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

# c <= b <= a とする

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

Submission status: Accepted

Solution code:
from bisect import bisect

n = int(input())
l = sorted(map(int, input().split()))
linv = l[::-1]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect_right

n, *L = map(int, open(0).read().split())
L.sort()
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += (bisect_right(L, L[i] + L[j] - 1) -
                bisect_right(L, L[j] - L[i]) - 1 - (L[j] - L[i] * 2 < 0))
print(ans // 3)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect_right

n, *L = map(int, open(0).read().split())
L.sort()
ans = 0
c = [0] * (2 * 10**3 + 1)
for i in range(2 * 10**3 + 1):
    c[i] = bisect_right(L, i)
for i in range(n):
    for j in range(i + 1, n):
        ans += c[L[i] + L[j] - 1] - c[L[j] - L[i]] - 1 - (L[j] - L[i]*2 < 0)
print(ans//3)

Submission status: Accepted

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

import bisect
l.sort()
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        idx = bisect.bisect_left(l,l[i]+l[j])
        #print('idx',idx)
        if j < idx:
            cnt += idx - j - 1


print(cnt)

Submission status: Accepted

Solution code:
import itertools, bisect

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

ans = 0
for i, j in itertools.combinations(range(N), 2):
    ans += bisect.bisect_left(L, L[i] + L[j]) - j - 1
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 i in range(len(l)-2):
  for j in range(i+1,len(l)):
    k = bisect.bisect_left(l, l[i]+l[j])
    if k > j:
      ans += k - j -1

print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
L = LI()
# L = np.array(_L)
#C = np.zeros(N + 1)

# def test(a,b,c):
#     if a<b+c and b<c+a and c<a+b:
#         return True
#     return False

# count = 0
# for pair in itertools.combinations(L, 3):
#     # print(pair)
#     if test(*pair):
#         count += 1
# print(count)

# for i in range(N):
#     for j in range(i+1,N):

from numba import njit
 
@njit
def f(A):
  count = 0
  for i in range(N):
    for j in range(i + 1, N):
      for k in range(j + 1, N):
        count += (A[k] < A[i] + A[j])
  return count
 
A = np.array(L)
A.sort()
print(f(A))

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    L = read_ints()
    L.sort()
    answer = 0
    for i in range(2, N):
        for j in range(1, i):
            start, end = -1, j
            while end-start > 1:
                mid = start+(end-start)//2
                if L[i]-L[j] < L[mid]: # valid
                    end = mid
                else:
                    start = mid
            answer += j-end
    return answer


if __name__ == '__main__':
    print(solve())

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

import bisect

count = 0
for i in range(n-1):
    for j in range(i+1, n):
            ab = l[i] + l[j]
            right = bisect.bisect(l, ab-1)
            left = j + 1
            count += (right - left)

print(count)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Ls = list(mapint())
Ls.sort()

from bisect import bisect_left
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(Ls, Ls[i]+Ls[j])
        ans += idx-1-j

print(ans)

Submission status: Accepted

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

# In[9]:


import bisect


# In[10]:


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


# In[11]:


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


# In[ ]:

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):
        a, b = L[i], L[j]
        c = a - b + 1
        if c > b: continue
        ans += (j - bisect.bisect_left(L, c))
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):
    ans+=max(bisect.bisect_left(l,l[i]+l[j])-j-1,0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

Lli.sort()

res = 0

for i in range(N-2):
  for j in range(i+1,N-1):
    ab = Lli[i]+Lli[j]
    res += bisect_left(Lli,ab)-j-1
    
print(res)

Submission status: Accepted

Solution code:
import math
import sys
from collections import Counter
import bisect
readline = sys.stdin.readline


def main():
    cnt = 0
    n = int(readline().rstrip())
    L = sorted(list(map(int, readline().rstrip().split())))
    for a in range(0, n - 2):
        for b in range(a + 1, n - 1):
            k = L[a] + L[b]
            index = bisect.bisect_left(L, k)
            cnt += index - b - 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))+[0]
l.sort(reverse=True)
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        left = j
        right = n
        while right - left > 1:
            middle = (left + right)//2
            if l[i]-l[j] < l[middle]:
                left = middle
            else:
                right = middle
        ans += (left-j)
print(ans)

Submission status: Accepted

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

def binary_search(a,b):
  top = N
  bottom = b
  c = (top + bottom)//2
  while top - bottom > 1:
    #print(a,b,":",top,bottom,c)
    if L[c] < L[a] + L[b]:
      bottom = c
    else:
      top = c
    c = (top + bottom)//2
  return top - 1

cnt = 0
for a in range(N-2):
  for b in range(a+1,N-1):
    cnt += binary_search(a,b) - b

print(cnt)

Submission status: Accepted

Solution code:
# D - Triangles
import bisect

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

ans=0

for i in range(N):
    for j in range (i+1,N):
        a=Li[i]+Li[j]
        t=bisect.bisect_left(Li,a)
        ans+=t-(j+1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
for a_i in range(N-2):
    for b_j in range(a_i+1, N-1):
        c_idx = bisect.bisect_left(L, L[a_i]+L[b_j])
        if c_idx > b_j:
            ans += c_idx - b_j - 1
print(ans)

Submission status: Accepted

Solution code:

def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort(reverse=True)

    count = 0
    for a_i in range(N-2):
        b_i = a_i + 1
        c_i = 1
        while b_i + c_i < N:

            if not is_triangle(L[a_i], L[b_i], L[-c_i]):
                c_i += 1

            else:
                count += (N - b_i - c_i)
                b_i += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    # print(L)
    ans = 0
    import bisect
    for i in range(N):
        for j in range(i+1, N):
            a, b = L[i], L[j]
            idx1 = bisect.bisect_left(L,b+a)
            idx2 = bisect.bisect_right(L,b-a)
            cnt = idx1 - idx2
            if idx2 <= i <= idx1:
                cnt -= 1
            if idx2 <= j <= idx1:
                cnt -= 1
            if cnt > 0:
                ans += cnt
            # print("a: {} b: {} i: {} j: {} idx1: {}, idx2: {}".format(a, b, i, j, idx1, idx2))
            # print(ans)
    print(ans//3)
    

if '__main__' == __name__:
    resolve()

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): # aを固定
    for j in range(i+1, n-1): # bを固定
        ab = L[i] + L[j]
        idx = bisect.bisect_left(L, ab, lo=j)
        ans += max(idx - (j+1), 0)

print(ans)