제출 #1218918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218918		recapp	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	584 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct SegTree {
    int n;
    vector<int> st;

    SegTree(int _n) : n(_n), st(4 * n, INT_MIN) {}

    void update(int p, int val) {
        update(1, 0, n - 1, p, val);
    }

    int query(int L, int R) {
        return query(1, 0, n - 1, L, R);
    }

    void update(int node, int l, int r, int p, int val) {
        if (l == r) {
            st[node] = max(st[node], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid)
            update(node << 1, l, mid, p, val);
        else
            update(node << 1 | 1, mid + 1, r, p, val);
        st[node] = max(st[node << 1], st[node << 1 | 1]);
    }

    int query(int node, int l, int r, int L, int R) {
        if (r < L || R < l) return INT_MIN;
        if (L <= l && r <= R) return st[node];
        int mid = (l + r) >> 1;
        return max(query(node << 1, l, mid, L, R), query(node << 1 | 1, mid + 1, r, L, R));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll m;
    cin >> n >> m;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<ll> vals = arr;
    vals.push_back(0);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto idx = [&](ll x) {
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin());
    };

    int v = vals.size();
    SegTree st(v);

    st.update(idx(0), 0);

    int best = 0;
    for (int i = 0; i < n; i++) {
        ll needed = arr[i] - m;
        int lo = int(lower_bound(vals.begin(), vals.end(), needed) - vals.begin());
        if (lo < 0) lo = 0;

        int bestPrev = st.query(lo, v - 1);
        int curDp = bestPrev + 1;

        best = max(best, curDp);

        st.update(idx(arr[i]), curDp);
    }

    cout << (n - best) << endl;

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37