提出 #17047530

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
using i64 = long long;

template <typename T, typename F>
class SegmentTree {
    T id;
    F f;
    const int size;
    std::vector<T> dat;

    T query_impl(const int a, const int b, const int k, const int l, const int r) const {
        if (r <= a || b <= l) return id;
        if (a <= l && r <= b) return dat[k];
        return f(query_impl(a, b, k * 2 + 1, l, (l + r) / 2),
                 query_impl(a, b, k * 2 + 2, (l + r) / 2, r));
    }

    template <class Predicate>
    int find_leftmost(const int a, const int b, Predicate pred, const int k, const int l, const int r) {
        if (r <= a || b <= l) return size;
        if (a <= l && r <= b) {
            if (!pred(dat[k], r - l)) return size;
            if (r - l == 1) return l;
        }
        const int cand = find_leftmost(a, b, pred, k * 2 + 1, l, (l + r) / 2);
        return cand < size ? cand : find_leftmost(a, b, pred, k * 2 + 2, (l + r) / 2, r);
    }

    template <class Predicate>
    int find_rightmost(const int a, const int b, Predicate pred, const int k, const int l, const int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) {
            if (!pred(dat[k], r - l)) return -1;
            if (r - l == 1) return l;
        }
        const int cand = find_rightmost(a, b, pred, k * 2 + 2, (l + r) / 2, r);
        return cand >= 0 ? cand : find_rightmost(a, b, pred, k * 2 + 1, l, (l + r) / 2);
    }

    static int calc_size(const int n) {
        int ret = 2;
        while (ret < n) ret *= 2;
        return ret;
    }

public:
    enum class FindDirection {
        Left,
        Right,
    };

    SegmentTree(const int n, const T &id, F f)
        : id(id)
        , f(f)
        , size(calc_size(n))
        , dat(2 * size - 1, id) {}

    template <template <class> class Container, class U>
    SegmentTree(const Container<T> &v, const U &id, F f)
        : id(id)
        , f(f)
        , size(calc_size(v.size()))
        , dat(2 * size - 1, id)
    {
        std::copy(v.begin(), v.end(), dat.begin() + size - 1);
        dig(0);
    }

    void dig(const int v) {
        if (v >= size - 1) return;
        dig(2 * v + 1);
        dig(2 * v + 2);
        dat[v] = f(dat[2 * v + 1], dat[2 * v + 2]);
    }

    void update(int i, const T x) {
        i += size - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    T query(const int a, const int b) const {
        return query_impl(a, b, 0, 0, size);
    }

    template <class Predicate>
    int find(const int l, const int r, FindDirection dir, Predicate pred) {
        return dir == FindDirection::Left
            ? find_leftmost(l, r, pred, 0, 0, size)
            : find_rightmost(l, r, pred, 0, 0, size);
    }

    T operator[](const int i) const {
        return dat[i + size - 1];
    }
};

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    SegmentTree st(300100, 0, [](const auto lhs, const auto rhs) { return std::max(lhs, rhs); });
    for (const int e : a) {
        const int l = std::max(e - k, 0), r = std::min(300001, e + k + 1);
        st.update(e, st.query(l, r) + 1);
    }

    std::cout << st.query(0, 300001) << std::endl;

    return 0;
}

提出情報

ジャッジ結果