Phạm vi phủ sóng trạm phát

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm Buổi 08 — Contest Chặng 1
Points
14
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Trên một con đường thẳng có $N$ ngôi nhà tại các tọa độ $x_1, x_2, \dots, x_N$. Nhà mạng thực hiện $Q$ truy vấn thử nghiệm: nếu đặt vùng phủ sóng trong đoạn $[L, R]$ thì có bao nhiêu ngôi nhà nằm trong vùng phủ sóng?

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, Q$. Dòng thứ hai chứa $N$ số nguyên $x_i$ (chưa chắc đã sắp xếp). $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L, R$ ($L \le R$).

Dữ liệu ra

$Q$ dòng, mỗi dòng là số ngôi nhà nằm trong đoạn $[L, R]$.

Ví dụ
Input Output
5 3
10 2 5 8 5
1 5
5 10
6 7
3
4
0
3 2
1 2 3
0 4
2 2
3
1
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $-10^9 \le x_i, L, R \le 10^9$
Draft saved