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

ans = 0
# print(A)
# print(B)
# print(C)
for i in range(n):
    b = B[i]
    pos_a = bisect_left(A, b)
    pos_c = bisect_right(C, b)
    ans += pos_a * (n - pos_c)
    # print(b, pos_a, pos_c)
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())))
bl = [0]*n
blli = [0]*n
al = [0]*n
alli = [0]*n
import bisect

for i in range(n):
    bl[i]=n-bisect.bisect(c,b[i])

blli[0] = sum(bl)
for i in range(n-1):
    blli[i+1] = blli[i]-bl[i]
   
for i in range(n):
    al[i]=n-bisect.bisect(b,a[i])

for i in range(n):
    if al[i]!=0:
        alli[i] = blli[-al[i]]

print(sum(alli))

Submission status: Accepted

Solution code:
def getval():
    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()
    return n,a,b,c 

def main(n,a,b,c):
    def bs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]>=key:
                hi = idx-1
            else:
                lo = idx+1
        return hi

    arrb = []
    arrc = []
    for i in b:
        arrb.append(bs(a,i)+1)
    for i in c:
        arrc.append(bs(b,i)+1)
    for i in range(1,n):
        arrb[i] += arrb[i-1]
    ans = 0
    for i in arrc:
        if i!=0:
            ans += arrb[i-1]
    print(ans)

if __name__=="__main__":
    n,a,b,c = getval()
    main(n,a,b,c)

Submission status: Accepted

Solution code:
import bisect

def main():
    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 in B:
        ans += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def binary_search(lst, t, i):
    left = -1
    right = len(lst)

    while abs(right - left) > 1:
        mid = (left + right) // 2
        if i == 0:
            if lst[mid] < t:
                left = mid
            else:
                right = mid
        elif i == 1:
            if lst[mid] > t:
                right = mid
            else:
                left = mid

    return left


def main():
    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 in B:
        a = binary_search(A, b, 0)
        c = binary_search(C, b, 1)
        ans += (a + 1) * (n - c - 1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

def binary_search_section(list, min, max):
    low = 0
    high = len(list) - 1
    upper = len(list)
    lower = -1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess >= min:
            high = mid - 1
        else:
            low = mid + 1
            lower = mid
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess > max:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1

    return [lower, upper]

def main():
    # ------ 入力 ------#
    # 1行入力
    n = int(input())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字
    bList = list(map(int, input().split()))     # スペース区切り連続数字
    cList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    aListSorted = sorted(aList)
    bListSorted = sorted(bList)
    cListSorted = sorted(cList)

    result = 0
    # for a in aListSorted:
    #     sec = binary_search_section(bListSorted, a+1, bListSorted[-1])
    #     for j in range(sec[0]+1, len(bListSorted)):
    #         b = bListSorted[j]
    #         sec2 = binary_search_section(cListSorted, b+1, cListSorted[-1])
    #         result += len(cListSorted) - (sec2[0] + 1)
    for b in bListSorted:
        sec = binary_search_section(aListSorted, aListSorted[0], b-1)
        sec2 = binary_search_section(cListSorted, b+1, cListSorted[-1])
        result += (sec[1] - sec[0] - 1)*(sec2[1] - sec2[0] - 1)

    # ------ 出力 ------#
    print("{}".format(result))
    # if flg == 0:
    #     print("YES")
    # else:
    #     print("NO")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
Bs = list(map(int,input().split()))
Cs = list(map(int,input().split()))

As.sort(reverse = True)
Bs.sort(reverse = True)
Cs.sort(reverse = True)

ls = [0]
sum = 0
for i in range(N):
    l = 0
    r = N-1
    while(r-l>1):
        mid = (l+r)//2
        if Cs[mid] <= Bs[i]:
            r = mid
        else:
            l = mid
    if Cs[0] <= Bs[i]:
        r = 0
    if Cs[N-1] > Bs[i]:
        r = N
    sum += r
    ls.append(sum)

ans = 0
for i in range(N):
    l = 0
    r = N-1
    while(r-l>1):
        mid = (l+r)//2
        if Bs[mid] <= As[i]:
            r = mid
        else:
            l = mid
    if Bs[0] <= As[i]:
        r = 0
    if Bs[N-1] > As[i]:
        r = N
    ans += ls[r]

print(ans)

Submission status: Accepted

Solution code:
import bisect as bs

def main():
    with open(0) as f:
        N = int(f.readline())
        A = sorted(list(map(int, f.readline().split())))
        B = list(map(int, f.readline().split()))
        C = sorted(list(map(int, f.readline().split())))

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

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())))
ans = 0
import bisect
b = []
for i in B:
    x = bisect.bisect_right(C,i)
    b.append(N-x)
y = sum(b)
c = [y]
for i in range(1,N):
    y -= b[i-1]
    c.append(y)
c.append(0)
for i in A:
    a = bisect.bisect_right(B,i)
    ans += c[a]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from numpy import cumsum

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
B_ = [0]*N
ans = 0
start = 0
for i, b in enumerate(B):
    j = bisect_left(A, b, start)
    B_[i] = j
    start = j
B_ = cumsum(B_)
start = 0
for c in C:
    i = bisect_left(B, c, start)
    start = i
    if i != 0:
        ans += B_[i-1]
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 b in B:
    a = bisect.bisect_left(A, b)
    c = bisect.bisect_right(C, b)
    ans += a*(n-c)

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
al = sorted(list(map(int, input().split())))
bl = sorted(list(map(int, input().split())))
cl = sorted(list(map(int, input().split())))
ans = 0

for b in bl:
    i = bisect.bisect_left(al, b)
    j = bisect.bisect_right(cl, b)
    ans += i*(n-j)

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:
    ans+=(n-bisect.bisect(c,i))*bisect.bisect_left(a,i)

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:
    A=bisect.bisect_left(a,i)
    B=len(b)-bisect.bisect_right(c,i)
    ans+=A*B
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
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):
  s=b[i]
  k=bisect_left(a,s)*(N-bisect_right(c,s))
  ans+=k
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    return N, A, B, C


def get_lb(l: list, key: int) -> int:
    """
    l[index] > keyとなる最小のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] > keyとなる最小のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess > key:
            high = mid
        else:
            low = mid
    return high


def get_ub(l: list, key: int) -> int:
    """
    l[index] < keyとなる最大のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] < keyとなる最大のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess < key:
            low = mid
        else:
            high = mid
    return low


def main(N: int, A: list, B: list, C: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): パーツの数(1 <= N <= 10**5)
        A (list): 上部のパーツのサイズ(1 <= A_i <= 10**9)
        B (list): 中部のパーツのサイズ(1 <= B_i <= 10**9)
        C (list): 下部のパーツのサイズ(1 <= C_i <= 10**9)
    """
    # 事前にリストをソートしておく
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)

    # 求解処理
    ans = 0
    for i in range(N):
        B_i = B[i]
        ans += (get_ub(A, B_i) + 1) * (N - get_lb(C, B_i))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A, B, C = get_input()

    # メイン処理
    main(N, A, B, C)

Submission status: Accepted

Solution code:
def solve():
    def bin_l(arr, key):
        l = 0
        r = len(arr) - 1
        while l <= r:
            mid = (l + r)//2
            if arr[mid] > key:
                r = mid - 1
            else:
                l = mid + 1
            
        if l < len(arr):
            return l
        else:
            return None
    
    def bin_s(arr, key):
      l = 0
      r = len(arr) - 1
      while l <= r:
        mid = (l + r) // 2
        if arr[mid] >= key:
          r = mid - 1
        else:
          l = mid + 1
      
      if r >= 0 :
        return r
      else:
        return None
        
    n = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A = sorted(A)
    C = sorted(C)
    
    sum = 0
    for b in B:
        a = bin_s(A, b)
        c = bin_l(C, b)
        a = a + 1 if a is not None else None
        c = n - c if c is not None else None
        if a is not None and c is not None:
            sum += a*c
    
    print(sum)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def bin_l(arr, key):
    l = 0
    r = len(arr) - 1
    while l <= r:
        mid = (l + r)//2
        if arr[mid] > key:
            r = mid - 1
        else:
            l = mid + 1
        
    if l < len(arr):
        return l
    else:
        return None

def bin_s(arr, key):
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = (l + r) // 2
    if arr[mid] >= key:
      r = mid - 1
    else:
      l = mid + 1
  
  if r >= 0 :
    return r
  else:
    return None
    
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A = sorted(A)
C = sorted(C)

sum = 0
for b in B:
    a = bin_s(A, b)
    c = bin_l(C, b)
    a = a + 1 if a is not None else None
    c = n - c if c is not None else None
    if a is not None and c is not None:
        sum += a*c

print(sum)

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

A.append(float("INF"))
AB = [0] * (N+1)
j = 0
for i in range(N):
    while A[j] < B[i]:
        j += 1
        if j == N:
            break
    AB[i+1] = AB[i] + j

ans = 0
B.append(float("INF"))
j = 0
for i in range(N):
    while B[j] < C[i]:
        j += 1
        if j == N:
            break
    ans += AB[j]

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate
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()
bs = [0]*N
for i in range(N):
    b = B[i]
    ai = bisect_left(A, b)
    bs[i] = ai
bs = [0]+list(accumulate(bs, lambda x,y:x+y))
ans = 0
for i in range(N):
    c = C[i]
    bi = bisect_left(B, c)
    ans += bs[bi]
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=sorted(a)
b=sorted(b)
c=sorted(c)
c.insert(0,-1)
c.append(10**10)
a.insert(0,-1)
a.append(10**10)
ans=0
for i in range(n):
    x=b[i]
    l=0
    r=n+1
    while r-l>1:
        m=(l+r)//2
        if a[m]<x:
            l=m
        else:
            r=m
    L=0
    R=n+1
    while R-L>1:
        M=(L+R)//2
        if c[M]<=x:
            L=M
        else:
            R=M
    ans+=l*(n+1-R)
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=sorted(a)
b=sorted(b)
c=sorted(c)
c.insert(0,-1)
c.append(10**10)
B=[0]*n
ans=0
for i in range(n):
    x=b[i]
    l=0
    r=n+1
    while r-l>1:
        m=(l+r)//2
        if c[m]>x:
            r=m
        elif c[m]<=x:
            l=m
    B[i]=n-l
g=[0]*n


g[n-1]=B[n-1]
for i in range(n-1):
    g[-2-i]=g[-1-i]+B[-2-i]
g.append(0)

b.insert(0,-1)
b.append(10**10)
for i in range(n):
    x=a[i]
    l=0
    r=n+1
    while r-l>1:
        m=(l+r)//2
        if b[m]>x:
            r=m
        elif b[m]<=x:
            l=m
    ans+=g[l]
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
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:
    ans+=(n-bisect(C,b))*bisect_left(A,b)
print(ans)

Submission status: Accepted

Solution code:
INF = 10**13
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
cusumB = [0 for i in range(N+1)]
C += [INF]
left = 0
for i, bi in enumerate(B):
    while C[left]<=bi:
        left += 1
    cusumB[i] = N - left
for i in range(N, 0, -1):
    cusumB[i-1] += cusumB[i]
B += [INF]
left = 0
ans = 0
for i, ai in enumerate(A):
    while B[left]<=ai:
        left += 1
    ans += cusumB[left]
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()

import bisect
As = list(range(N+1))

Bs = [0] * N
s = 0
for i,b in enumerate(B):
    ind = bisect.bisect_left(A,b)
    s += As[ind]
    Bs[i] = s
Bs = [0] + Bs
Cs = [0] * N
ans = 0
for i,c in enumerate(C):
    ind = bisect.bisect_left(B,c)
    ans += Bs[ind]

print(ans)

Submission status: Accepted

Solution code:
def bin_src_l(arr, key):
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = (l + r) // 2
    if arr[mid] > key:
      r = mid - 1
    else:
      l = mid + 1
  
  if l < len(arr):
    return l
  else:
    return None

def bin_src_s(arr, key):
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = (l + r) // 2
    if arr[mid] >= key:
      r = mid - 1
    else:
      l = mid + 1
  
  if r >= 0 :
    return r
  else:
    return None


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

sum = 0
for b in B:
  a = bin_src_s(A, b)
  c = bin_src_l(C, b)
  a = a + 1 if a is not None else None
  c = N - c if c is not None else None
  if a is not None and c is not None:
    sum += a * c
  
print(sum)

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

if a[0] > b[-1] or b[0] > c[-1]:
    print(0)
    exit()

# fix index of b
bi = 0
lb = []
for ai in range(n):
    while bi < n and a[ai] >= b[bi]:
        lb.append(ai)
        bi += 1
while bi < n:
    lb.append(n)
    bi += 1

ans = 0
ci = n - 1
for bi in range(n-1, -1, -1):
    while ci >= 0 and b[bi] < c[ci]:
        ci -= 1
    ans += lb[bi] * (n - ci - 1)

print(ans)

Submission status: Accepted

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

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

print(cnt)

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()
C.sort()

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

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*(N-c)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)
count = [0]*N
answer = 0
z = 0
for i in range(N):
    if B[N-1] >= C[i]:
        break
    z += 1
count[N-1] = z
for i in range(1, N):
    k=z
    for j in range(k):
        if B[N-1-i] < C[k-1-j]:
            break
        else:
            z -= 1      
    count[N-1-i] = z
sum_matrix = [0]*(N+1)
y = 0
for i in range(N):
    sum_matrix[i+1] = sum_matrix[i] + count[i]
for i in range(N):
    if A[N-1] >= B[i]:
        break
    answer += count[i]
    y += 1
for i in range(1, N):
    x = y
    for j in range(x):
        if A[N-1-i] < B[x-1-j]:
            break        
        y -= 1
    answer += sum_matrix[y]
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from bisect import bisect, bisect_left

    N = int(input())
    A = sorted([int(x) for x in input().split()])
    B = [int(x) for x in input().split()]
    C = sorted([int(x) for x in input().split()])

    print(sum([bisect_left(A, b) * (N - bisect(C, b)) for b in B]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from bisect import bisect, bisect_left

    N = int(input())
    A = sorted([int(x) for x in input().split()])
    B = sorted([int(x) for x in input().split()])
    C = sorted([int(x) for x in input().split()])

    print(sum([bisect_left(A, b) * (N - bisect(C, b)) for b in B]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from bisect import bisect

    N = int(input())
    A = sorted([int(x) for x in input().split()])
    B = sorted([int(x) for x in input().split()])
    C = sorted([int(x) for x in input().split()])

    lst = [N - bisect(C, b) for b in B]
    lst = lst[::-1]
    tmp_lst = [lst[0]]
    for i in lst[1:]:
        tmp_lst.append(i + tmp_lst[-1])
    tmp_lst = tmp_lst[::-1]

    ans = 0
    for a in A:
        res = bisect(B, a)
        ans += tmp_lst[res] if res < N else 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right as br 
from bisect import bisect_left as bl

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


B2=[]
C2=[]
for b in B:
    B2.append(bl(A,b))
for c in C:
    C2.append(bl(B,c))
    
B3=[]
for b in B2:
    if B3:
        B3.append(B3[-1]+b)
    else:
        B3.append(b)
    
res=sum([B3[C2[i]-1] if C2[i]!=0 else 0 for i in range(N)])
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 b in range(N):
    a=bisect.bisect_left(A,B[b])
    c=N-bisect.bisect_right(C,B[b])
    ans+=a*c
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
lsA = list(map(int,input().split()))
lsB = list(map(int,input().split()))
lsC = list(map(int,input().split()))
lsA.sort()
lsB.sort()
lsC.sort()
ans = 0
for i in range(N):
    B = lsB[i]
    indexA = bisect.bisect(lsA,B-1)
    indexC = N - bisect.bisect(lsC,B)
    ans += indexA*indexC
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 b in B:
    a = bisect.bisect_right(A, b-1)
    c = len(C)-bisect.bisect_right(C, b)
    ans += a*c
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**10
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))+[INF]
C = sorted(list(map(int,input().split())))+[INF]
AB = [0]*N
BC = [0]*N
j = 0
for i in range(N):
    while A[i] >= B[j]:
        j += 1
    if j < N:
        AB[j] += 1
for i in range(N-1):
    AB[i+1] += AB[i]
j = 0
cur = 0
ans = 0
for i in range(N):
    while C[i] > B[j]:
        cur += AB[j]
        j += 1
    ans += cur
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a,b,c=map(list,[sorted(list(map(int, input().split()))) for i in range(3)])
ans=0
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:
import bisect
n = int(input())
a, b, c = map(list, [sorted(list(map(int, input().split()))) for i in range(3)])
ans = 0
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:
import bisect
import itertools

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)

Submission status: Accepted

Solution code:
N = int(input())
As = sorted(map(int, input().split()))
Bs = sorted(map(int, input().split()))
Cs = sorted(map(int, input().split()))

A_ind = 0
C_ind = 0
ans = 0
for B in Bs:
    while A_ind < N and As[A_ind] < B:
        A_ind += 1
    while C_ind < N and Cs[C_ind] <= B:
        C_ind += 1
    ans += A_ind * (N - C_ind)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    A = NLI()
    B = NLI()
    C = NLI()
    
    A = sorted(A)
    C = sorted(C)
    
    ans = 0
    
    for b in B:
        

        A_ng = -1       #ng:とり得る最小の値-1
        A_ok = len(A)  #ok:とり得る最大の値+1

        while (abs(A_ok - A_ng) > 1):
            A_mid = (A_ok + A_ng) // 2

            if A[A_mid] >= b:#計算の結果、midが条件を満たすならokにmidを代入。そうでなければngにmidを代入。
                A_ok = A_mid
            else:
                A_ng = A_mid
                
        C_ng = -1      #ng:とり得る最小の値-1
        C_ok = len(C)  #ok:とり得る最大の値+1

        while (abs(C_ok - C_ng) > 1):
            C_mid = (C_ok + C_ng) // 2

            if C[C_mid] > b:#計算の結果、midが条件を満たすならokにmidを代入。そうでなければngにmidを代入。
                C_ok = C_mid
            else:
                C_ng = C_mid
                
                
        len_C = len(C)
        
        ans += A_ok * (len_C-C_ok)
        
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def abc077c_snuke_festival():
    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())))
    total = 0
    for i in range(n):
        b_size = b[i]
        j = bisect.bisect_left(a, b_size)
        j = n - j
        k = bisect.bisect_right(c, b_size)

        total += (n - j) * (n - k)
    print(total)


abc077c_snuke_festival()

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_left(A, 13))

ct_AB = [0 for _ in range(N)] 
for i in range(N):
  ct_AB[i] = bisect.bisect_left(A, B[i])

ct_AB_sum = [0 for _ in range(N)] 
ct_AB_sum[0] = ct_AB[0]
for i in range(1,N):
  ct_AB_sum[i] = ct_AB[i] + ct_AB_sum[i-1]
  
ans = 0
for i in range(N):
  j = bisect.bisect_left(B, C[i]) - 1
  #print(i, j, ct_AB_sum[j])
  if j >= 0:
    ans += ct_AB_sum[j]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from bisect import bisect, bisect_left
    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()
    C.sort()
    ans = 0
    for b in B:
        a = bisect_left(A, b)
        c = N - bisect(C, b)
        ans += a*c
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = sorted(inpl())
B = sorted(inpl())
C = sorted(inpl())

ans = 0
for b in B:
    tmp = bisect.bisect_right(C,b)
    tmp2 = bisect.bisect_left(A,b)
    ans += (n-tmp) * tmp2

print(ans)

Submission status: Accepted

Solution code:
from bisect import *
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()
pat_b = [0]*N
for i in range(N):
    b = B[i]
    pat_b[i] = bisect_left(A, b)
    pat_b[i] *= (N - bisect_right(C, b))

print(sum(pat_b))

Submission status: Accepted

Solution code:
def upper_bound(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s+t)//2
        if A[m] > x:
            t = m
        else:
            s = m
    
    return t

def lower_bound(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s+t)//2
        if A[m] >= x:
            t = m
        else:
            s = m
    
    return t


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 in B:
    ans += lower_bound(A, b) * (N - upper_bound(C, b))

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect,bisect_left
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 in B:
  i=bisect_left(A,b)
  j=bisect(C,b)
  ans+=i*(N-j)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

import bisect as bs
import numpy as np
A.sort()
C.sort()
#B_a:b未満のAのパーツ数、B_c:b超のCのパーツ数
B_a = np.array([bs.bisect_left(A,b) for b in B]) 
B_c = np.array([N-bs.bisect_right(C,b) for b in B])
ans = np.dot(B_a, B_c)
print(ans)