A21555 LYZ滑冰 全站首杀AK

#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

const int MAXN = 200005;
ll max_val[4 * MAXN];
ll lazy[4 * MAXN];

ll n, m, k, d;

void push_up(int u) {
    max_val[u] = std::max(max_val[u * 2], max_val[u * 2 + 1]);
}

void push_down(int u) {
    if (lazy[u] != 0) {
        max_val[u * 2] += lazy[u];
        lazy[u * 2] += lazy[u];
        max_val[u * 2 + 1] += lazy[u];
        lazy[u * 2 + 1] += lazy[u];
        lazy[u] = 0;
    }
}

void build(int u, int l, int r) {
    lazy[u] = 0;
    if (l == r) {
        max_val[u] = -1LL * (l + d) * k;
        return;
    }
    int mid = l + (r - l) / 2;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    push_up(u);
}

void update(int u, int l, int r, int update_l, int update_r, ll val) {
    if (update_l > update_r) {
        return;
    }
    if (update_l <= l && r <= update_r) {
        max_val[u] += val;
        lazy[u] += val;
        return;
    }
    push_down(u);
    int mid = l + (r - l) / 2;
    if (update_l <= mid) {
        update(u * 2, l, mid, update_l, update_r, val);
    }
    if (update_r > mid) {
        update(u * 2 + 1, mid + 1, r, update_l, update_r, val);
    }
    push_up(u);
}

ll query(int u, int l, int r, int query_l, int query_r) {
    if (query_l > query_r) {
        return -2e18; 
    }
    if (query_l <= l && r <= query_r) {
        return max_val[u];
    }
    push_down(u);
    int mid = l + (r - l) / 2;
    ll res = -2e18;
    if (query_l <= mid) {
        res = std::max(res, query(u * 2, l, mid, query_l, query_r));
    }
    if (query_r > mid) {
        res = std::max(res, query(u * 2 + 1, mid + 1, r, query_l, query_r));
    }
    return res;
}

void solve() {
    std::cin >> n >> m >> k >> d;

    build(1, 1, n);

    for (int i = 0; i < m; ++i) {
        ll r, x;
        std::cin >> r >> x;
        
        update(1, 1, n, r, n, x);
        
        ll max_b = 0;
        if (n - d >= 1) {
            max_b = query(1, 1, n, 1, n - d);
        }

        if (max_b <= 0) {
            std::cout << "TAK\n";
        } else {
            std::cout << "NIE\n";
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}