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: Runtime Error

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

d = 0
e = 0
ans = 0
for i in b:
    while i > a[min(d,n-1)] and d <= n-1:
        d += 1
    while i >= c[e] and e < n:
        e += 1
    ans += d*(n-e)

print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import *

import numpy as np

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = sorted(reads())
B = sorted(reads())
C = sorted(reads())

numB = [0] * N
for i in range(N):
  numB[i] = N - bisect_left(C, B[i]+1)
print(numB, file=stderr)

anumB = [0] * (N+1)
for i in range(N):
  anumB[i+1] = anumB[i] + numB[i]
print(anumB, file=stderr)

numA = [0] * N
for i in range(N):
  numA[i] = anumB[N] - anumB[bisect_left(B, A[i]+1)]
print(numA, file=stderr)

print(sum(numA))

Submission status: Runtime Error

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

ans = 0
#print(A)
#print(C)
for b in B:
    lenA = bisect.bisect_left(A,b) #競合時は無事無視される
    lenC = N - bisect.bisect_left(C,b) if b not in C else N - C.index(b) - 1
    ans += lenA*lenC
    #print(lenA,lenC)
    
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;

int a[100010];
int b[100010];
int c[100010];

ll bc[100010];
ll ans;

int main()
{
	read(n);
	for(int i=1; i<=n; ++i) read(a[i]);
	for(int i=1; i<=n; ++i) read(b[i]);
	for(int i=1; i<=n; ++i) read(c[i]);
	sort(a+1, a+n+1);
	sort(b+1, b+n+1);
	sort(c+1, c+n+1);
	for(int i=n, p=n+1; 1<=i; --i){
		while(1<p && b[i]<c[p-1]) --p;
		bc[i]=n-p+1;
	}
	ll tmp = 0;
	for(int i=n, p=n+1; 1<=i; --i){
		while(1<p && a[i]<b[p-1]) tmp += bc[--p];
		ans += tmp;
	}
	printf("%lld\n", ans);
	return 0;
}

Submission status: Runtime Error

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 binary_search(x,i):
	low = 0
	high = len(x)
	t = (low + high) // 2 
	while (low<=high):
		if (i==x[t]):
			break
		elif (i > x[t]):
			low = t + 1
		elif (i < x[t]):
			high = t - 1
		t = (low + high) // 2
	return t

ans=0
for i in range(n):
  b_l=binary_search(b,a[i])
  for j in range(b_l+1,n):
    c_l=binary_search(c,b[j])
    ans+=n-c_l-1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

N  = int(input())
As = list(map(int, input().split(' ')))
Bs = list(map(int, input().split(' ')))
Cs = list(map(int, input().split(' ')))

As.sort()
Bs.sort()
Cs.sort()

cnt = 0

for a in As:
    b_idx = bisect.bisect_left(Bs, a)

    while Bs[b_idx] == a and b_idx < len(Bs):
        b_idx += 1

    if b_idx >= len(Bs):
        continue

    for bi in range(b_idx, len(Bs)):
        c_idx = bisect.bisect_left(Cs, Bs[bi])

        while Cs[c_idx] == Bs[bi] and c_idx < len(Cs):
            c_idx += 1

        cnt += max(0, len(Cs) - c_idx)

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    K,N = map(int,input().split())

    if K % 2 == 0:
        ans = [K//2]
        for i in range(N-1):
            ans.append(K)
    else:
        back = N // 2
        mid = K // 2 + 1
        ans = [mid for i in range(N)]
        for i in range(back):
            if ans[-1] == 1:
                ans.pop()
            else:
                ans[-1] -= 1
                while len(ans) < N:
                    ans.append(K)
    print(''.join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
a = list(map(float, input().split(" ")))
b = list(map(float, input().split(" ")))
c = list(map(float, input().split(" ")))

sort(a)
sort(c)

def binary_insert_right(li, v):
    upper = len(li)
    lower = 0
    while upper > lower:
        mid = ( upper + lower ) // 2
        if v < li[mid]:
            upper = mid
        else:
            lower = mid - 1
    return mid

num = 0
for i in range(N):
    num += binary_insert_right(a, b[i]) * ( len(c) - binary_insert_right(c, b[i]) - 1 )
print(num)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
A = list(set(map(int, input().split())))
B = list(set(map(int, input().split())))
C = list(set(map(int, input().split())))
ans = 0
A.sort()
B.sort()
C.sort()
# print(A, B, C)
for i in range(N):
    b = B[i]
    a_i = bisect.bisect_left(A, b)
    c_i = bisect.bisect_right(C, b)
    cnt = (a_i) * (N - c_i)
    # print(b, a_i, c_i, cnt)
    ans += cnt

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a_list = input().split()
a_list = [int(a) for a in a_list]

b_list = input().split()
b_list = [int(b) for b in b_list]

c_list = input().split()
c_list = [int(c) for c in c_list]

a_ar = np.array(a_list)
b_ar = np.array(b_list)
c_ar = np.array(c_list)

b_count_ar = np.sum(b_ar[:,np.newaxis]<c_ar,axis=1)
# print(b_count_ar)
a_count = (a_ar[:,np.newaxis]<b_ar).astype(int)
# print(a_count)

print(np.sum(a_count * b_count_ar))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
a = np.array( list(map(float, input().split(" "))) )
b = np.array( list(map(float, input().split(" "))) )
c = np.array( list(map(float, input().split(" "))) )

# sort(a)
# sort(b)
# sort(c)

mem_a = np.zeros(10**5) - 1

dict_c = {}
def count_c(v):
    key = v
    if v in dict_c:
        return dict_c[v]
    else:
        val = len(np.where( (v < c) == True )[0])
        dict_c.update({key:val})
        return val

num = 0
for i in range(N):
    n = len(np.where( (a[i] < b) == True )[0])
    if mem_a[n] == -1:
        mem_a[n] = 0
        for j in range(N):
            mem_a[n] += count_c(b[j])
    num += mem_a[n]
print(num)

Submission status: Runtime Error

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()
ins_c = [0]*n
ins_b = [0]*n
parts_comb = [0]*n
for i in range(n) :
    ins_c = bisect.bisect_right(c, b[i])
    ins_b = bisect.bisect_right(b, a[i])
ans = 0
for i in range(n) :
    for j in range(ins_b[i], n) :
        ans += n - r_c

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(lambda x: int(x)-1, input().split())))


    BC = []
    for i in range(N):
        b = B[i]
        BC.append(N - bisect_left(C, b))

    Cum = []
    S = sum(BC)
    tmp = S
    for i in range(N):
        Cum.append(tmp)
        tmp -= BC[i]
    Cum.append(0)

    count = 0
    for i in range(N):
        a = A[i]
        count += Cum[bisect_right(B, a)]

    print(count)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a_list = input().split()
a_list = [int(a) for a in a_list]

b_list = input().split()
b_list = [int(b) for b in b_list]

c_list = input().split()
c_list = [int(c) for c in c_list]

a_ar = np.array(a_list)
b_ar = np.array(b_list)
c_ar = np.array(c_list)

# a_ar.sort()
# b_ar.sort()
# c_ar.sort()

# b_count = []
# for b in b_ar:
#     b_count.append(len(c_ar[c_ar>b]))
b_count_ar = np.sum(b_ar[:,np.newaxis]<c_ar,axis=1)


# b_count_ar = np.array(b_count)

# count = 0
# for a in a_ar:
# count += b_count_ar[np.where(b_ar>a)[0]].sum()
    
print(np.sum((a_ar[:,np.newaxis]<b_ar).astype(int) * b_count_ar))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")

from bisect import bisect, bisect_left, bisect_right



# Find rightmost value less than x
def find_lt(a, x):
    i = bisect_left(a, x)
    if i:
        return i
    raise ValueError



# Find leftmost value greater than x'
def find_gt(a, x):
    i = bisect_right(a, x)
    if i != len(a):
        return i
    raise ValueError




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

    ans = 0
    for b in B:
        a = find_lt(A, b)
        b = N - find_gt(C, b)
        ans += a * b
    print(ans)


if __name__ == '__main__':
    main()