Problem:


Score : 300 points

Problem Statement

The season for Snuke Festival has come again this year. First of all, Ringo will perform a ritual to summon Snuke. For the ritual, he needs an altar, which consists of three parts, one in each of the three categories: upper, middle and lower.

He has N parts for each of the three categories. The size of the i-th upper part is A_i, the size of the i-th middle part is B_i, and the size of the i-th lower part is C_i.

To build an altar, the size of the middle part must be strictly greater than that of the upper part, and the size of the lower part must be strictly greater than that of the middle part. On the other hand, any three parts that satisfy these conditions can be combined to form an altar.

How many different altars can Ringo build? Here, two altars are considered different when at least one of the three parts used is different.

Constraints

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9(1\leq i\leq N)

1 \leq B_i \leq 10^9(1\leq i\leq N)

1 \leq C_i \leq 10^9(1\leq i\leq N)

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N
B_1 ... B_N
C_1 ... C_N

Output

Print the number of different altars that Ringo can build.

Sample Input 1

2
1 5
2 4
3 6

Sample Output 1

3

The following three altars can be built:

Upper: 1-st part, Middle: 1-st part, Lower: 1-st part

Upper: 1-st part, Middle: 1-st part, Lower: 2-nd part

Upper: 1-st part, Middle: 2-nd part, Lower: 2-nd part

Sample Input 2

3
1 1 1
2 2 2
3 3 3

Sample Output 2

27

Sample Input 3

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288

Sample Output 3

87



Sample input:
2
1 5
2 4
3 6


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
B.sort()
C.sort()

cnt = 0
tmp = N
while tmp != 0:
  cnt += 1
  tmp //= 2

def binary_search(v, L, M, m):
  if M <= v:
    return 0
  elif m > v:
    return N
  else:
    l, r = 0, N
    d = (l + r) // 2
    for _ in range(cnt):
      if L[d] <= v:
        l = d + 1
        d = (l + r) // 2
      else:
        r = d
        d = (l + r) // 2
    return N - d
MB, mB, MC, mC = B[N-1], B[0], C[N-1], C[0]
LB = [binary_search(B[_], C, MC, mC) for _ in range(N)]
for i in range(N-1, 0, -1):
  LB[i-1] += LB[i]
S = 0
for i in range(N):
  X = N - binary_search(A[i], B, MB, mB)
  if X != N:
    S += LB[X]
print(S)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from bisect import bisect_left
def main():
    n=int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))

    A.sort()
    C.sort()
    sum=0
    for i in range(n):
        cnt=1
        cnt*= bisect_left(A,B[i])
        cnt*= n-bisect_right(C,B[i])
        sum+=cnt 

    print(sum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
upper = sorted(list(map(int, input().split())))
middle = list(map(int, input().split()))
lower = sorted(list(map(int, input().split())))

ans = 0
for m in middle:
    idx_u = bisect_left(upper, m)
    idx_l = N-bisect_right(lower, m)
    ans += idx_u*idx_l
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
# print(A)
# print(B)
# print(C)
ans = 0
for b in B:
    aindex = bisect.bisect_left(A,b)
    cindex = bisect.bisect_right(C,b)
    # print(aindex,cindex)
    ans += aindex*(n-cindex)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = [int(i) for i in input().split()]
    c = [int(i) for i in input().split()]
    a.sort()
    b.sort()
    c.sort()

    cnt = 0
    for i in range(n):
        v = b[i]
        idx_a = bisect_left(a, v) 
        idx_b = bisect_right(c, v)
        cnt += idx_a * (n-idx_b)     
    print(cnt)
main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort() ; B.sort() ; C.sort()
import bisect as bi

ans=0

for i in B:
    ans+= bi.bisect_left(A,i) * (n-bi.bisect_right(C,i))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import bisect
#N, Q = map(int,input().split())
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
B.sort()
C.sort()
B_num = [0] * N
ans = 0
for i in range(N):
    b = B[i]
    B_num[i] += N - 1 - bisect.bisect_right(C,b) + 1

for i in range(N-1):
    B_num[i+1] += B_num[i]
#print(B_num)
B_num = [0] + B_num

for i in range(N):
    a = A[i]
    idx = min(bisect.bisect_right(B, a), N)
    ans += B_num[N] - B_num[idx]
    #print(B_num[idx], ans)
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()

ablist = [0]*N
r = 0

for i in range(N):
  ablist[i] = bisect.bisect_left(A, B[i]) + ablist[i-1]

for i in range(N):
  a = bisect.bisect_left(B, C[i])
  if a > 0:
    r += ablist[a-1]
  
print(r)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0
for b_i in b:
  s_a=bisect.bisect_left(a,b_i)
  s_c=n-bisect.bisect_right(c,b_i)
  ans+=s_a*s_c
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ans = 0
a = tuple(a); b = tuple(b); c = tuple(c)
a = sorted(a)
b = sorted(b,reverse=True)
c = sorted(c)

import bisect
chk_b = [0]*n
for i,bi in enumerate(b):
  y = bisect.bisect_right(c, bi)
  chk_b[i] = max(0,n-y) + chk_b[i-1]
  
chk_b = tuple(chk_b)
b = sorted(b)
for i in a:
  x = bisect.bisect_right(b, i)
  if x <= n-1:
    ans += chk_b[n-1-x]
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for i in range(N):
  b = B[i]
  a = bisect.bisect_left(A, b)
  c = N - bisect.bisect_right(C, b)
  ans += a*c
  
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
for i in range(n):
    b = B[i]
    a = bisect.bisect_left(A, b)
    c = n-bisect.bisect_right(C, b)
    ans += a*c
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

alters_count = 0
for b in B:
    aidx = bisect_left(A, b)
    cidx = bisect_right(C, b)
    if cidx == N:
        continue
    alters_count += aidx * (N - cidx)

print(alters_count)

Submission status: Accepted

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

A.sort()
C.sort()
ans = 0
for i in range(N):
    #print(bisect.bisect_left(A, B[i]), bisect.bisect_right(C, B[i]))
    ans += bisect.bisect_left(A, B[i])*(N-bisect.bisect_right(C, B[i]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
a, b, c = np.sort(np.array(sys.stdin.read().split(), dtype=np.int64).reshape(3, n), axis=1)

def main():
    combs = np.sum(np.searchsorted(a, b) * (n - np.searchsorted(c, b, side='right')))
    print(combs)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
a, b, c = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(3, n)
a.sort(); c.sort()

def main():
    print(np.sum(np.searchsorted(a, b) * (n - np.searchsorted(c, b, side='right'))))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r

n = int(sys.stdin.readline().rstrip())
a = sorted(map(int, sys.stdin.readline().split()))
b = sorted(map(int, sys.stdin.readline().split()))
c = sorted(map(int, sys.stdin.readline().split()))

def main():
    combs = 0
    for x in b:
        combs += bi_l(a, x) * (n - bi_r(c, x))
    print(combs)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
# print(bisect.bisect(A,4))
    
ans = 0
for b in B:
    aindex = bisect.bisect_left(A,b)
    cindex = bisect.bisect_right(C,b)
    # print(b,aindex,(len(C)-cindex))
    ans += aindex*(len(C)-cindex)

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
C.sort()

res = 0
for j in B:
    i = bisect.bisect_left(A, j)
    k = bisect.bisect_right(C, j)
    k = len(C) - k
    res += i * k

print(res)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

ans = 0
for i in range(n):
  canA = bisect.bisect_left(A, B[i])
  canC = bisect.bisect_right(C, B[i])
  ans += (canA)*(n-canC)
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ansum = 0
for B in b:
    index = bisect.bisect_left(a,B)
    index2= bisect.bisect_right(c,B)
    ansum += index*(n-index2)
print(ansum)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
d = [-1] * n
ansum = 0
def stat(array,par):
    return bisect.bisect(array,par)

for i in range(n):
    indexC = stat(c,b[i])
    d[i] = max(0,n-indexC) 
for i in range(n-1):
    d[n-i-2] += d[n-i-1]
for A in a:
    index = stat(b,A)
    if index < n:
        ansum += d[index]
print(ansum)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

ans = 0

for b in B:
    ans += bisect_left(A,b) * (N - bisect_right(C,b))

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, bisect
n = int(input())
alis = sorted(list(map(int, input().split())))
blis = list(map(int, input().split()))
clis = sorted(list(map(int, input().split())))
ans = 0
for b in blis:
    up = bisect_left(alis, b)
    down = n - bisect(clis, b)
    ans += up*down
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
tops = list(map(int, input().split()))
middles = list(map(int, input().split()))
bottoms = list(map(int, input().split()))
tops.sort()
middles.sort()
bottoms.sort()
# print(tops)
# print(middles)
# print(bottoms)
# top<middle<bottomでないといけない
# middleをfor文で繰り返して、topとbottomで二分探索をする。
# そしてそれ以下の数を出して、掛け算すれば組み合わせの数を出せる


def left_binary_search(target, nums):
    left = 0
    right = len(nums) - 1
    while left <= right:
        # 0+7 /2 = 3
        # print(left, right)
        mid = int((left + right) / 2)
        # print(f'mid: {mid}')
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            right = mid - 1

    # 0,1,2,3,4
    # 2
    # => return 2
    # print(left, right)
    return left


def right_binary_search(target, nums):
    left = 0
    right = len(nums) - 1
    while left <= right:
        # 0+7 /2 = 3
        # print(left, right)
        mid = int((left + right) / 2)
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    # 0,1,2,3,4
    # 2
    # => return 2
    # print(left, right)
    return left


count = 0
for middle in middles:
    top_index = left_binary_search(middle, tops)
    bottom_index = right_binary_search(middle, bottoms)
    # print(top_index, bottom_index, (top_index) * (len(bottoms) - bottom_index))
    count += (top_index) * (len(bottoms) - bottom_index)
print(count)

Submission status: Accepted

Solution code:
#二分探索...ソートした配列を二つに分けて、どちらに入るか調べることで高速化
import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

#リストを整列する
a.sort()
b.sort()
c.sort()

#二分探索で、それぞれのbについて、a<bになるaの個数を調べる
#二分探索で、それぞれのbについて、c>bになるcの個数を調べる
ans = 0
for i in range(n):
	ab = bisect.bisect_left(a,b[i])	#a==bの場合を除外する
	tmpbc = bisect.bisect_right(c,b[i])#b==cの場合を一度含んでおく
	bc = n-tmpbc
	
	ans += ab*bc
	
print(ans)

Submission status: Accepted

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

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A)
B = sorted(B)
C = sorted(C)

res = 0
for b in B:
    index_a = bisect.bisect_left(A, b)
    index_c = bisect.bisect_right(C, b)
    res += index_a * (N - index_c)

print(res)

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""
# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7

def main():
  import bisect # 二分探索
  n = int(input())
  A = sorted(map(int,input().split()))
  B = map(int,input().split())
  C = sorted(map(int,input().split()))
  print(sum(bisect.bisect_left(A,b) * (n-bisect.bisect_right(C,b)) for b in B))
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

i = 0
AB_comb = [0] * N
for b in range(N):
    tmp = AB_comb[b - 1]
    while i < N and A[i] < B[b]:
        tmp += 1
        i += 1
    AB_comb[b] += tmp

i = 0
ABC_comb = [0] * N
for c in range(N):
    tmp = ABC_comb[c - 1]
    while i < N and B[i] < C[c]:
        tmp += AB_comb[i]
        i += 1
    ABC_comb[c] += tmp

print(sum(ABC_comb))

"""
import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
for i in range(N):
    upi = bisect.bisect_left(A, B[i])
    dwi = bisect.bisect_right(C, B[i])
    ans += upi*(N - dwi)

print(ans)
"""

Submission status: Accepted

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
b_ls = list(map(int, input().split()))
c_ls = list(map(int, input().split()))
a_ls.sort()
b_ls.sort()
c_ls.sort()

# 「-より大きい」
def isOK_1(ind, key, ls):
    if ls[ind] > key:
        return True
    else: # if ls[ind] <= key
        return False


def connect_b2c_minind(key, ls):
    ok = len(ls)
    ng = -1
    while ok - ng > 1:
        mid = ng + (ok-ng) // 2
        if isOK_1(mid, key, ls):
            ok = mid
        else:
            ng = mid
    return len(ls) - ok

def isOK_2(ind, key, ls):
    if ls[ind] < key:
        return True
    else: # if ls[ind] >= key
        return False

def connect_a2b_maxind(key, ls):
    ok = -1
    ng = len(ls)
    while ng - ok > 1:
        mid = ok + (ng - ok) // 2
        if isOK_2(mid, key, ls):
            ok = mid
        else:
            ng = mid
    return ok + 1

ans = 0
for i in range(n):
    ans += connect_a2b_maxind(b_ls[i], a_ls) * connect_b2c_minind(b_ls[i], c_ls)
print(ans)

Submission status: Accepted

Solution code:
import bisect
#2分探索の際に用いる
N = int(input())
L_a = [int(s) for s in input().rstrip().split(" ")]
L_b = [int(s) for s in input().rstrip().split(" ")]
L_c = [int(s) for s in input().rstrip().split(" ")]
L_a.sort()
L_b.sort()
L_c.sort()
k = 0
for i in range(N):
  s_l = bisect.bisect_left(L_a, L_b[i]) #L_b[i]よりも真に小さい配列の要素の数
  s_r = bisect.bisect_right(L_c, L_b[i])
  k += s_l*(N-s_r)
print(k)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for b in B:
    a = bisect.bisect_left(A, b)
    c = bisect.bisect_right(C, b)
    ans += a * (len(C)-c)
print (ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
for i in range(N):
    upi = bisect.bisect_left(A, B[i])
    dwi = bisect.bisect_right(C, B[i])
    ans += upi*(N - dwi)

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [int(i) for i in input().split(' ')]
B = [int(i) for i in input().split(' ')]
C = [int(i) for i in input().split(' ')]

A.sort()
B.sort()
C.sort()

count = 0
for b in B:
    i = bisect.bisect_left(A,b)
    j = bisect.bisect_right(C,b)
    count += i * (N - j)

print(count)

Submission status: Accepted

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

ans = 0
for i in b:
  ai = bisect.bisect_left(a, i)
  # print(ai)
  ci = n - bisect.bisect_right(c, i)
  # print(ci)
  ans += ai*ci
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
b = LI()
b.sort()
c = LI()
c.sort()
A = []
B = []
ans = 0
for i in b:
    r = br(c,i)
    B.append(n-r)
B = [0] + list(accumulate(B))
for i in a:
    r = br(b,i)
    ans += B[-1] - B[r]
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for i in b:
  ai = bisect.bisect_left(a, i)
  # print(ai)
  ci = n - bisect.bisect_right(c, i)
  # print(ci)
  ans += ai*ci
print(ans)


# 2
# 1 5
# 2 4
# 3 6

# 6
# 3 14 159 2 6 53
# 58 9 79 323 84 6
# 2643 383 2 79 50 288

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for i in b:
  ai = bisect.bisect_left(a, i)
  ci = n - bisect.bisect_right(c, i)
  ans += ai*ci
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

i = 0
AB_comb = [0] * N
for b in range(N):
    tmp = AB_comb[b - 1]
    while i < N and A[i] < B[b]:
        tmp += 1
        i += 1
    AB_comb[b] += tmp

i = 0
ABC_comb = [0] * N
for c in range(N):
    tmp = ABC_comb[c - 1]
    while i < N and B[i] < C[c]:
        tmp += AB_comb[i]
        i += 1
    ABC_comb[c] += tmp

print(sum(ABC_comb))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)


def solve():

    N = iip()
    A = iip(True)
    B = iip(True)
    C = iip(True)

    A.sort()
    B.sort()
    C.sort()

    def ruisekiwa(l):
        ret = []
        cur = 0
        for i in l:
            cur += i
            ret.append(cur)
        return ret



    nb = [bisect_left(A, i) for i in B]
    snb = ruisekiwa(nb)

    #print(A)
    #print(B)
    #print(C)

    #print("")
    #print(nb)
    #print(snb)

    id = [bisect_right(B, i-1) -1 for i in C]
    id = [i for i in id if i != -1]
    nc = [snb[min(i, len(B)-1)] for i in id]

    #print(nc)
    #print(id)

    print(sum(nc))




#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# import bisect

N = INT()
A = LIST()
B = LIST()
C = LIST()

A.sort()
B.sort()
C.sort()

def binsearch(lst, th, ud="up"):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if ud == "up":
            if lst[mid] > th:
                right = mid
            else:
                left = mid
        else:
            if lst[mid] >= th:
                right = mid
            else:
                left = mid
        
    return right if ud == "up" else left


ans = 0
# for ai in A:
#     i = bisect.bisect_right(B, ai)
#     for bi in B[i:]:
#         j = bisect.bisect_right(C, bi)
#         ans += len(C[j:])

for bi in B:
    i = binsearch(A, bi, "down")
    j = binsearch(C, bi, "up")
    ans += (i+1) * (N-j)


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort()
list_B.sort()
list_C.sort()
b = 0
list_UP = []
for i in range(n):
    while True:
        if b > n-1 or list_A[i] < list_B[b]:
            break
        b += 1
    list_UP.append(n-b)


c = 0
list_DOWN = []
for i in range(n):
    while True:
        if c > n-1 or list_B[i] < list_C[c]:
            break
        c += 1
    list_DOWN.append(n-c)


ans = 0
num = 0
sum_value = sum(list_DOWN)
for i in list_UP:
    while True:
        if num == n-i:
            break
        sum_value -= list_DOWN[num]
        num += 1
    ans += sum_value

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

def binsearch2(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] > threshold:
            right = mid
        else:
            left = mid
    return right

def binsearch1(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left

ans = 0
for b in B:
    AtoB = binsearch1(b, A)
    BtoC = binsearch2(b, C)
    ans += (AtoB + 1) * (N - BtoC)
print(ans)