소프티어

문제의 특성은 데이터가 너무 크다는 것이고 O(NQ)만 되도 벌써 시간초과가 뜰 것입니다.

다만 여기서 큰 힌트 2가지를 통해 시간복잡도를 선형으로 대폭 줄일 수 있습니다.

1. 중앙값을 구할 수 있는 경우의 수만 찾으면 됨
2. 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다.

1번 조건은 말 그대로입니다. 중앙값이란 [1,2,3,5,8] 데이터에서도 3 [1,2,3,100,288] 데이터에서도 3입니다. 쉽게 설명하자면 인덱스만 알면 나머지 데이터가 어떻게 생겼든 상관이 없습니다.

저희는 3이 될 수 있는 조합만 찾으면 되는데 3대만 뽑는다는 건 어떻게 뽑아도 [(O), M, (O)] 가 되게끔만 해주는 "경우의 수"만 찾으면 됩니다.

그렇다면 정렬을 해놓고 (median 이전에 나오는 숫자의 개수 x 이후에 나오는 숫자의 개수) 로 그 조합을 찾을 수 잇습니다.

2번 조건은 1번 조건을 위한, 더 빨리 풀 수 있도록 하는 힌트입니다. 서로 다름을 가정 = 각 숫자마다 index 부여 가능

따라서 저희가 찾고자 하는 median 의 index를 미리 부여해놓으면 찾을 수 있습니다.

아래는 이것을 구현한 코드이며 아래와 같은 복잡도를 가집니다.

TC : O(NlogN)~=O(Q) (NlogN이 23만 정도 됩니다)

SC : O(N)

감사합니다!

import sys
input = sys.stdin.readline

def solve(median):
    m_idx = index.get(median, None)
    if median == data[0] or median == data[-1] or not m_idx:
        return 0
    
    return m_idx * (n-m_idx-1)

if __name__ == "__main__":
    n, q = map(int, input().split())
    data = list(map(int, input().split()))
    data.sort()
    index = {d:i for i, d in enumerate(data)}

    for _ in range(q):
        median = int(input())
        print(solve(median))