Two pointer 1B
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.
Mảng \(c\) gồm \(m\) phần tử được xác định như sau:
\(c_i\) = số phần tử trong mảng \(a\) có giá trị nhỏ hơn \(b_i\)
Hãy xác định mảng \(c\)
Constants
-
\(1 \leq n, m \leq 10^5\)
-
\(0 \leq a_i, b_i \leq 10^9\)
Example
Test 1
Input
6 7
1 6 9 13 18 18
2 3 8 13 15 21 25Output
1 1 2 3 4 6 6
Bình luận
Hint
duyệt theo mảng b, tìm vị trí đầu tiên của mảng a mà giá trị lớn hơn hoặc bằng b, in ra vị trí đó trừ 1 (do mảng đã đc sắp xếp nên độ phức tạp chỉ tầm O(n)
6 bình luận nữa