Submission #1218915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218915		recapp	Rabbit Carrot (LMIO19_triusis)	C++17	Compilation error	0 ms	0 KiB

triusis

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

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, 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;
}

Compilation message (stderr)

triusis.cpp: In constructor 'SegTree::SegTree(int)':
triusis.cpp:13:40: error: 'INT_MIN' was not declared in this scope
   13 |     SegTree(int _n) : n(_n), st(4 * n, INT_MIN) {
      |                                        ^~~~~~~
triusis.cpp:3:1: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
    2 | #include <iostream>
  +++ |+#include <climits>
    3 | #include <vector>
triusis.cpp: In member function 'int SegTree::query(int, int, int, int, int)':
triusis.cpp:40:36: error: 'INT_MIN' was not declared in this scope
   40 |         if (r < L || R < l) return INT_MIN;
      |                                    ^~~~~~~
triusis.cpp:40:36: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?