문제
n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오.
입력
첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문에 해당하는 숫자 범위는 100,000,000이하이다.
출력
각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.
예제 입력
10 4
1 3 4 3 2 3 1 2 5 10
1 3 9 10
예제 출력
2 3 0 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
def lower_bound(n, i):
s = 0
e = len(n) - 1
while s < e:
m = (s + e) // 2
if n[m] < i:
s = m + 1
else:
e = m
return s
def upper_bound(n, i):
s = 0
e = len(n) - 1
while s < e:
m = (s + e) // 2
if n[m] <= i:
s = m + 1
else:
e = m
return s
a, b = list(map(int, input().split()))
n = list(map(int, input().split()))
n.sort()
n.append(100000001)
k = list(map(int, input().split()))
for i in k:
idx2 = upper_bound(n, i)
idx1 = lower_bound(n, i)
print(idx2 - idx1)
|
cs |