Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).
Input
- Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
- Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)
Output
- In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\)
- Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.
Example
Test 1
Input
5
3 2 1 1 2
Output
4 2 0 0 2
Bình luận
Bài này hay nhất là dùng lower_bound
This comment is hidden due to too much negative feedback. Click here to view it.
hyt
test sai sai
bài này quy hoạch động ac nè
...
Spoiler Alert
Hint 1
Reference 90 score + TLE code | \(O(n ^ 2)\) time | \(O(n)\) query | \(O(1)\) auxiliary space | Brute-force
Hint 2
Hint 3
Hint 4
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(log_2 n)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search, STL
Cho em hỏi hình như test 9 và 10 của bài này hình như a[i] có = 0 đúng không ạ? tại em code thôi đề là nguyên dương thì wa 2 test đó còn khi em code có thêm trường hợp ai = 0 thì ac :'(. Không biết có phải là do em code sai không nữa