Một khu vui chơi gần bờ biển trải dài và hẹp, được chia thành \(n\) khu vực, đánh số từ \(1\) đến \(n\) và các khu vực được xem như nằm trên cùng một đường thẳng.
Để giám sát an ninh và hoạt động trong các khu vui chơi, Ban quản lý đã lắp đặt các cameras tại một số khu vực. Họ đã lắp đặt \(q\) cameras tại các khu vực \(c_1, c_2, \ldots, c_q\). Một khu vực có thể lắp đặt một hoặc nhiều cameras hoặc không. Nếu có cameras lắp đặt tại khu vực \(i\) thì cameras đó sẽ giám sát sát các khu vực \(i-r, \ldots, i-1, i, i+1, \ldots, i+r\); tức là ngoài khu vực \(i\) thì cameras có thể giám sát \(r\) khu vực bên trái và \(r\) khu vực bên phải của \(i\) (nếu có ít hơn \(r\) khu vực bên phải hoặc bên trái thì cameras sẽ chỉ giám sát các khu vực trong phạm vi đó).
Yêu cầu: Hãy giúp Ban quản lý xác định xem tại mỗi khu vực trong khu vui chơi có thể được giám sát bởi bao nhiêu cameras?
Input
Dữ liệu vào từ tập văn bản CAU4.INP gồm:
- Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\);
- Dòng thứ hai chứa hai số nguyên \(q, r\) \((1 \le q \le 10^5, 0 \le r < n)\);
- Dòng thứ ba chứa \(q\) số nguyên \(c_1, c_2, \ldots, c_q\) \((1 \le c_i \le n,\ i = 1,2,\ldots,q)\).
Các số trên một dòng cách nhau dấu cách.
Output
Ghi ra tập văn bản CAU4.OUT gồm một dòng ghi \(n\) số nguyên cách nhau dấu cách, số thứ \(i\) là số lượng cameras giám sát khu vực \(i\).
Example
Test 1
Input
8
5 2
5 3 7 1 3Output
3 3 4 3 4 2 2 1Note
Ví dụ 1: Có \(8\) khu vực trong khu vui chơi, có \(5\) cameras và bán kính giám sát của chúng là \(2\). Cameras thứ nhất tại khu vực \(5\) sẽ giám sát các khu vực \(3, 4, 5, 6, 7\). Cameras thứ hai tại khu vực \(3\) sẽ giám sát các khu vực \(1, 2, 3, 4, 5\). Cameras thứ ba tại khu vực \(7\) sẽ giám sát các khu vực \(5, 6, 7, 8\). Cameras thứ tư tại khu vực \(1\) sẽ giám sát chính khu vực \(1, 2, 3\). Cameras cuối cùng cũng tại khu vực \(3\) sẽ giám sát các khu vực \(1, 2, 3, 4, 5\).
Ví dụ 2: Bán kính giám sát của cameras bằng \(0\) nên cameras được lắp đặt tại khu vực nào chỉ giám sát được khu vực đó.
Test 2
Input
5
4 0
1 2 1 3Output
2 1 1 0 0Scoring
- \(20\%\) số tests tương ứng với \(20\%\) số điểm của bài có \(r = 0\);
- \(40\%\) số tests tương ứng với \(40\%\) số điểm của bài có \(n, q \le 7000\);
- \(20\%\) số tests khác tương ứng với \(20\%\) số điểm của bài có \(n \le 7000\);
- \(20\%\) số tests còn lại tương ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.