Tìm Kiếm Nhị Phân Hai Biên

Binary-search Buổi 75-76 — Stress Test
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một mảng đã sắp xếp không giảm gồm $N$ số nguyên $a_1, a_2, \dots, a_N$ và $Q$ truy vấn. Mỗi truy vấn cho một số nguyên $x$, hãy tìm vị trí đầu tiên và vị trí cuối cùng (đánh số từ $1$) của $x$ trong mảng. Nếu $x$ không xuất hiện, in ra -1 -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $Q$ ($1 \le N, Q \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $a_1 \le a_2 \le \dots \le a_N$ ($-10^9 \le a_i \le 10^9$).
  • $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$ ($-10^9 \le x \le 10^9$).
Dữ liệu ra
  • Với mỗi truy vấn, in ra hai số nguyên là vị trí đầu tiên và cuối cùng của $x$, hoặc -1 -1.
Ví dụ
Input Output
5 3
1 2 2 2 5
2
3
5
2 4
-1 -1
5 5
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $-10^9 \le a_i, x \le 10^9$
Draft saved