TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tp = N
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 
            ans += tp
            break
        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)

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 
            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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# coding: utf-8
# Your code here!
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):
        insert_index = bisect.bisect_left(l,l[i]+l[j])
        ans+=(insert_index)
        
print(ans)


# coding: utf-8
# Your code here!
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):
        insert_index = bisect.bisect_left(l,l[i]+l[j])
        ans+=(insert_index-j-1)
        
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

i = "218 786 704 233 645 728 389"
L = list(map(int, i.split()))



L.sort()

print(L)

l1 = 0
l2 = 1
l3 = 2
ans = 0
while l1 < N - 2:
    while l3 < N: 
      if L[l1] + L[l2] > L[l3]:
        l3 += 1
      else:
        ans += cmb(l3 - l1 + 1, 3) 
        l2 = l3 - 1
        l1 = l2 - 1
  
      if l3 == l2 + 1 and l2 == l1 + 1: 
        l3 += 1
      elif l2 == l1 + 1:
        l2 += 1
      else:
        l1 += 1

print(ans)

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

print(ans)

Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
# a - b < c
# b - a < c
# a + b > c

import bisect

n = int(input())

l = sorted([int(li) for li in input().split()])
print(l)

ret = 0

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

print(ret)


# a - b < c
# b - a < c
# a + b > c

import bisect

n = int(input())

l = sorted([int(li) for li in input().split()])
#print(l)

ret = 0

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

print(ret)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n = int(input())
ll = [int(w) for w in input().split()]
ll.sort(reverse=True)

ans = 0
for ei, i in enumerate(ll):
    for ej, j in enumerate(ll[ei + 1:]):
        ans += len([w for w in ll[ei + ej + 2] if w > i - j])

print(ans)


import bisect

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(ll, ll[i] + ll[j]) - (j + 1)

print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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.

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

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

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import bisect
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
L.reverse()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        x = L[i] - L[j]
        point = bisect.bisect_left(sorted(L),x)
        if x == L[N-1-point]:
            ans += max(0,N-j-1-point-1)
        else:
            
            ans += N-j-1-point if point < N-1-j else 0
        print(point)
        print(ans)
print(ans)

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
L.reverse()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
         
            print(L[i] >= L[j] + L[k])
            if L[i] >= L[j] + L[k]:
                break
            ans+=1
print(ans)

import bisect
N = int(input())
ans = 0
L = list(map(int,input().split()))
L = sorted(L)
for i in range(N-1):
    for j in range(i+1,N):
        a = bisect.bisect(L,L[i]+L[j]-1)
       
        ans += a-j-1

print(ans)        
         
        

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

import itertools as it

def main():
    N=ii()
    L=lmis()
    ans=0
    for a,b,c in it.combinations(L,3):
        if a+b<c: continue
        if a+c<b: continue
        if b+c<a: continue
        ans+=1
    print(ans)


if __name__ == "__main__":
    main()

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N=ii()
    L=sorted(lmis(),reverse=True)
    ans=0
    for i in range(N-2):
        a=L[i]
        j=i+1
        k=N-1
        while j<k:
            if a<L[j]+L[k]:
                j+=1
                ans+=k-j+1
            else:
                k-=1
    print(ans)


if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_right
N = int(input())
L = sorted([int(i) for i in input().split()])

res = 0

for i in range(N):
    for j in range(i+1, N):
        r = bisect_right(L, L[i]+L[j])
        res += max(r-(j+1), 0)

print(res)


from bisect import bisect_left
N = int(input())
L = sorted([int(i) for i in input().split()])

res = 0

for i in range(N):
    for j in range(i+1, N):
        r = bisect_left(L, L[i]+L[j])
        res += max(r-(j+1), 0)

print(res)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
def main():
    n = int(input())
    l_s = list(sorted(map(int, input().split(' '))))

    ans = 0

    for i in range(n-2):
        a = l_s[i]

        left = i+1
        for right in range(i+2, n):
            if l_s[right] <= a + l_s[left]:
                ans += right - left
            else:
                while l_s[right] >= a + l_s[left] or right-1 == left:
                    left += 1
                ans += right - left

    print(ans)


if __name__ == '__main__':
    main()


import bisect
import math

def main():
    n = int(input())
    l_s = list(sorted(map(int, input().split(' '))))

    ans = 0

    for c in range(2, n):
        for b in range(1, c):
            idx = bisect.bisect_right(l_s, l_s[c] - l_s[b])
            idx = min(b, idx)
            ans += b - idx
    print(ans)


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_left

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

l.sort()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    print(bisect_left(l,l[j]+l[i]),i,j,l)
    count+=bisect_left(l,l[j]+l[i])-j-1
print(count)

from bisect import bisect_left

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

l.sort()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    count+=bisect_left(l,l[j]+l[i])-j-1
print(count)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect, bisect_left
 
N= int(input())
L= list(map(int,input().split()))
L.sort()
 
ans = 0
for i in range(N-2):
  a=L[i]
  for k in range(i+1,n-1):
    b=s[k]
    t=bisect_left(L,a+b)
    ans+=t-k-1
print(ans)

import math
N=int(input())
listL=list(map(int,input().split()))
listL.sort()
ans=0
for i in range(N-1,2,-1):
  for k in range(i-1,1,-1):
    t=math.ceil(k/2)
    d=listL[i]-listL[k]
    half=math.ceil((k-t)/4)
    while (d-listL[t]<=0 or d-listL[t+1]>0) and t!=0 and t!=k-1:
      third=listL[t]
      if d-third>=0:
        t=t-half
      else:
        t=t+half
      half=half//2+1
      print(half,t) 
    ans+=k-t+1
print(ans)        

from bisect import bisect, bisect_left
 
N=int(input())
L=list(map(int,input().split()))
L.sort()
 
ans = 0
for i in range(N-2):
  a=L[i]
  for k in range(i+1,N-1):
    b=L[k]
    t=bisect_left(L,a+b)
    ans+=t-k-1
print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)
    
    

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)
    

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split())).sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx
print(res)

from bisect import bisect_left

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

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx-(j+1)

print(res)

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx
print(res

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L = L.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx
print(res)

from bisect import bisect_left

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

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L, L[i]+L[j])
        res += idx-(j+1)

print(res)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0

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


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

print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_left

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

counter = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        upper_bound = bisect_left(L, L[i] + L[j], j+1, N-1)
        counter += upper_bound - (j+1)
print(counter)

from itertools import combinations
from bisect import bisect_left

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

counter = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        upper_bound = bisect_left(L, L[i] + L[j], j+1, N)
        counter += upper_bound - (j+1)
print(counter)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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]
        ans += bs.bisect_left(L,s) - j - 1
        
        
        
        # (val < x for val in list[0:i]) + (val >= x for val in list[i:len(list)])
print(ans)

import bisect as bs
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]
        ans += bs.bisect_left(L,s) - j - 1
        
        
        
        # (val < x for val in list[0:i]) + (val >= x for val in list[i:len(list)])
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_right
from itertools import combinations_with_replacement

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

li = list(combinations_with_replacement(l, 2))
li = [x for x in li if x[0] != x[1] and x[1] != max(l)]

ans = 0
for small, mid in li:
    right = bisect_right(l, small + mid - 1)
    left = bisect_left(l, mid)
    ans += max(right - left - 1, 0)

print(ans)

from bisect import bisect_left, bisect_right
from itertools import combinations_with_replacement

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

li = list(combinations_with_replacement(l, 2))
li = [x for x in li if x[0] != x[1]]

ans = 0
for small, mid in li:
    right = bisect_right(l, small + mid)
    left = bisect_left(l, mid)
    if right > left + 1:
        ans += right - left - 1

print(ans)

from bisect import bisect_left

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

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

print(ans)

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1, 1001):
    ans -= (N-CC[i-1]) * B[i]
print(ans)


k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
for i in range(N):
    B[i] += B[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1001):
    ans -= (N-CC[i-1]) * B[i]
print(ans)


k = 31
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(1001)]]

N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 1001
for a in A:
    C[a] += 1
B = li(st(nu(C) ** 2))
for a in A:
    if a <= 500: B[2*a] -= 1
for i in range(1001):
    B[i] //= 2
for i in range(1, 1001):
    C[i] += C[i-1]
ans = N*(N-1)*(N-2)//6
for i in range(1, 1001):
    ans -= (N-C[i-1]) * B[i]
print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import itertools

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
print(([num for num in list(itertools.combinations(nums, 3)) if num[0] + num[1] > num[2]]))

import bisect

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        ind = bisect.bisect_left(nums, nums[a] + nums[b])
        ans += ind - 1 - b
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
b_c= [0]*n
for i  in range(n-2):
    a = l[i]
    pre_k = 2
    for j in range(i+1,n-1):
        b = l[j]
        max_c = a+b-1
        k = bisect(l[j+pre_k-1:],max_c)
        ans += (pre_k-2 + )
print(ans)

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    if l[i]==a:
        continue
    a = l[i]
    b = 0
    for j in range(i+1,n-1):
        if l[j]==b:
            continue
        b = l[j]
        c = 0 
        for k in range(j+1,n):
            if l[k]==c:
                continue
            c = l[k]
            if c-b < a:
                ans += 1
            else:
                break
print(ans)

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

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
n = int(input())
l = list(map(int,input()))
import bisect
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        x = bisect.bisect_left(l[j+1:],l[i]+l[j])
        ans += x
print(ans)

n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())
L = list(map(int, input().split(" ")))
L.sort() 
counter = 0

for num_1, i in enumerate(L):
  for num_2, j in enumerate(L):
    if num_1 <= num_2:
      break
    else:
      for num_3, k in enumerate(L):
        if num_2 <= num_3:
          break
        else:
          if j + k <= i:
            break
          else:
            counter += 1
print(counter)

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() 
print(L)
counter = 0

for num_1, i in enumerate(L):
  for num_2, j in enumerate(L):
    if num_1 <= num_2:
      break
    else:
      for num_3, k in enumerate(L):
        if num_2 <= num_3:
          break
        else:
          if j + k <= i:
            continue
          else:
            counter += 1
print(counter)

import bisect

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() 
print(L)
counter = 0

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

import bisect

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

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

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())
L = map(int, input().split())

ans = 0
for aix in range(N):
    for bix in range(aix, N):
        for cix in range(cix, N):
            if L[aix] < L[bix] + L[cix] and L[bix] < L[aix] + L[cix] and L[cix] < L[aix] + L[bix]:
                ans += 1

print(ans)


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

import bisect

L.sort()
# print(L)

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

print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):

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



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

print(ans)


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



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

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
a = int(input())
b = [int(i) for i in input().split()]
print(sum(1 for x in range(a) for y in range(a) for z in range(a) if x!=y and y!=z and x!=z and (b[x]<b[y]+b[z] and b[y]<b[x]+b[z] and b[z]<b[x]+b[y]))/6)



a = int(input())
arr = [int(i) for i in input().split()]
arr.sort() 
count = 0
for i in range(0,a-2): 
    k = i + 2
    for j in range(i+1,a):
        while (k < a and arr[i] + arr[j] > arr[k]): 
            k += 1
        if(k>j): 
            count += k - j - 1
  
print(count)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):


import bisect

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = max(L_list[a] - L_list[b], L_list[b] - L_list[a], L_list[b])
        c_max = L_list[a] + L_list[b]
        count_c = bisect.bisect_right(L_list, c_max) - bisect.bisect_right(L_list, c_min)
        count += count_c

print(count)



import bisect

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = L_list[b + 1]
        c_max = L_list[a] + L_list[b]
        c_max_idx = bisect.bisect_left(L_list, c_max)
        c_count = c_max_idx - (b + 1)
        count += c_count

print(count)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

# import copy
# import heapq
# from collections import deque



INF = sys.maxsize
# MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = na()

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


if __name__ == '__main__':
    main()


import sys
import re
import math
import collections
import decimal
import bisect
import itertools

# import copy
# import heapq
# from collections import deque



INF = sys.maxsize
# MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = na()

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


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import bisect
n=int(input())
L=[int(x) for x in input().split()]
L.sort()
ans=0

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

import bisect
n=int(input())
l=[int(x) for x in input().split()]
l.sort()
ans=0

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

import bisect
n=int(input())
L=[int(x) for x in input().split()]
L.sort()
ans=0

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

import bisect
n=int(input())
L=[int(x) for x in input().split()]
L.sort()
ans=0

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

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):

def is_triangle(a, b, c):
    print(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 index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c_i = 1

            while not is_triangle(a, b, L[-c_i]):
                if c_i + b_i == N:
                    break
                c_i += 1

            count += (N - b_i - c_i)

    print(count)


if __name__ == '__main__':
    main()



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()


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

from itertools import accumulate
from scipy.misc import comb



#     if x <= 0:
#         return 1
#
#     return factorial(x - 1) * x
#
#

#     return factorial(n) / factorial(r) / factorial(n - r)


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

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            
            cnt = acm[k] - acm[b]

            
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += int(comb(nums[b], 3))
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += int(comb(nums[b], 2)) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()


from bisect import bisect_left

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

l.sort()

ans = 0
for i, a in enumerate(l):
    for j, b in enumerate(l[i+1:], i + 1):
        k = bisect_left(l, a + b)
        ans += k - j - 1

print(ans)


Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
N = str(input())
N = int(N)
Lines = input().split(" ")
Lines = list(map(int, Lines))
answer = 0

for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (Lines[lineI] + Lines[lineJ] > LinesInt[lineK]) and (Lines[lineK] + Lines[lineJ] > Lines[lineI]) and (Lines[lineK] + Lines[lineI] > Lines[lineJ]):
                answer += 1
print(answer)


N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0

import bisect

for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-j-1
print(answer)

N = str(input())
N = int(N)
Lines = input().split(" ")
Lines = list(map(int, Lines))
answer = 0

for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (Lines[lineI] + Lines[lineJ] > Lines[lineK]) and (Lines[lineK] + Lines[lineJ] > Lines[lineI]) and (Lines[lineK] + Lines[lineI] > Lines[lineJ]):
                answer += 1
print(answer)


N = str(input())
N = int(N)
Lines = input().split(" ")
LinesInt = map(int, Lines)
answer = 0
    
for lineI in range(len(N)):
    for lineJ in range(lineI+1,len(N)):
        for lineK in range(lineJ+1,len(N)):
             if (LinesInt[lineI] + LinesInt[lineJ] > LinesInt[lineK]) and (LinesInt[lineK] + LinesInt[lineJ] > LinesInt[lineI]) and (LinesInt[lineK] + LinesInt[lineI] > LinesInt[lineJ]):
                answer += 1
print(answer)

N = int(input())
Lines = list(map(int, input().split(" ")))
Lines.sort()
answer = 0
 
import bisect
 
for lineI in range(N):
    for lineJ in range(lineI+1,N):
    	answer += bisect.bisect_left(Lines,Lines[lineI]+Lines[lineJ])-lineJ-1
print(answer)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# N = int(input())

A = readlines()
print(A)
exit()


def f(v):
    left = 0
    right = N
    while left + 1 < right:
        x = (left + right) // 2
        if v > L[x]:
            left = x
        else:
            right = x
    return right


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        idx = f(L[i] + L[j])
        # print('a, b, idx', a, b, idx)
        # idx = np.searchsorted(L, a + b, sorter=None)
        ans += idx - 1 - j
print(ans)


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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import bisect

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

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

print(count)

import bisect

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

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

print(count)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect
N = int(input())
L = sorted([int(_) for _ in input().split()])
ans = 0
for a in range(N - 2):
    for b in range(a + 1, N - 1):
        
        ans += bisect(L, L[a] + L[b] ) - b - 1
print(ans)

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

Verdicts: Wrong Answer

Accepted