Chơi game

Sub 1: ~H_1~ ~<~ ~H_2~ ~<~ ... ~<~ ~H_n~

• Gọi ~f[i] = 1~ nếu tòa tháp ~i~ thỏa mãn và ~f[i] = 0~ trong trường hợp còn lại. Ta có ~f[1] = 1~
• Xét tòa tháp thứ ~i~, ta cần tìm xem có tòa tháp thứ ~j~ sao cho ~j < i~, ~|h[i] - h[j]| \le k~ và ~f[j] = 1~. Tuy nhiên vì ~h~ là dãy tăng dần, ta chỉ cần xét vị trí ~i - 1~ vì nếu vị trí ~i - 1~ thỏa mãn thì vị trí ~i~ sẽ thỏa mãn. Nếu không giả sử tồn tại vị trí ~t~ thỏa mãn ~f[t] = 1~ và ~t < i - 1~, lúc này ~|h[i] - h[i - 1]| < |h[i] - h[t]|~ nên nếu không thể cập nhật vị trí ~i~ từ ~i - 1~ thì càng không thể sử dụng ~t~ để cập nhật cho ~i~.
• ĐPT: ~O(n)~

Sub 2: ~n \le 1000~

• Xét vị trí thứ ~i~, ta duyêt qua các vị trí ~j < i~.
• Nếu tồn tại vị trí ~j~ thỏa mãn ~f[j] = 1~ và ~|h[i] - h[j] \le k~ thì ~f[i] = 1~.
• ĐPT: ~O(n ^ 2)~

Sub 3 : Không có ràng buộc gì thêm

• Nhận xét rằng ~i~ độ cao có thể nhảy đến từ đỉnh ~1~ sẽ tạo thành 1 khoảng ~[l_i, r_i]~. Ta có ~l_1 = h[1] - k~ và ~r_1 = h[1] + k~.
• Vậy với mỗi vị trí ~i + 1~, nếu ~l_i \le h[i + 1] \le r_i~ thì ~f[i + 1] = 1~.
• Ta cập nhật khoảng ~[l_i, r_i]~ mỗi khi có độ cao thỏa mãn mới.
• DDPT: ~O(n)~

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 2;

int n, k, h[N];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    #define task "CHOIGAME"
    if(fopen(task ".INP", "r")) {
        freopen(task ".INP", "r", stdin);
        freopen(task ".ANS", "w", stdout);
    }
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    int l = h[0], r = h[0];
    cout << "1 ";
    for (int i = 1; i < n; ++i) {
        if (l - k <= h[i] && h[i] <= r + k) {
            cout << "1 ";
            l = min(l, h[i]);
            r = max(r, h[i]);
        } else cout << "0 ";
    }
    cout << "\n";
    return 0;
}