Truy Vấn Cận Dưới (Lower Bound Binary Search)
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho mảng A gồm N số nguyên đã được sắp xếp tăng dần (chỉ số từ 1 đến N) và Q truy vấn. Với mỗi truy vấn gồm số nguyên X, hãy tìm chỉ số i nhỏ nhất (1 ≤ i ≤ N) sao cho A[i] ≥ X. Nếu không tồn tại phần tử nào ≥ X, in ra -1.
Dữ liệu vào (Input)
- Dòng 1: Hai số nguyên dương
NvàQ(1 ≤ N, Q ≤ 10^5). - Dòng 2:
Nsố nguyênA[1] ≤ A[2] ≤ ... ≤ A[N]. - Dòng 3:
Qsố nguyênXcần truy vấn.
Dữ liệu ra (Output)
- Gồm
Qdòng, mỗi dòng in ra chỉ số đầu tiên tìm được (1-indexed) hoặc-1.
Ví dụ mẫu
Sample Input 1
5 3
2 4 4 7 9
4 8 10
Sample Output 1
2
5
-1
Community Discussion