Đếm phần tử không vượt quá X (Upper Bound)

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm sorting
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho một dãy gồm $N$ số nguyên (chưa chắc đã sắp xếp) và $Q$ truy vấn. Với mỗi truy vấn là số nguyên $X$, hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị nhỏ hơn hoặc bằng $X$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $Q$. Dòng thứ hai chứa $N$ số nguyên. $Q$ dòng tiếp theo mỗi dòng chứa một số nguyên $X$.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng là số lượng phần tử $\le X$.

Ví dụ
Input Output
5 3\n7 2 5 2 9\n5\n1\n10 3\n0\n5
3 2\n4 4 4\n4\n3 3\n0
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |X| \le 10^9$.

Draft saved