Submission #1271966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271966		ceceg	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	2 ms	576 KiB

triusis

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

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

    int N; long long M;
    if (!(cin >> N >> M)) return 0;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    const int NEG = -1e9;

    vector<long long> vals = {0};
    vals.insert(vals.end(), a.begin(), a.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int K = (int)vals.size();

    int SZ = 1; while (SZ < K) SZ <<= 1;
    vector<int> seg(2 * SZ, NEG);

    auto pull = [&](int p){ for (p >>= 1; p; p >>= 1) seg[p] = max(seg[p<<1], seg[p<<1|1]); };

    auto update_value = [&](long long h, int v) {
        int p = int(lower_bound(vals.begin(), vals.end(), h) - vals.begin()) + SZ;
        seg[p] = max(seg[p], v);
        pull(p);
    };

    auto query_suffix = [&](long long t) {
        int l = int(lower_bound(vals.begin(), vals.end(), t) - vals.begin());
        if (l >= K) return NEG;
        int L = l + SZ, R = SZ + K - 1, res = NEG;
        while (L <= R) {
            if (L & 1) res = max(res, seg[L++]);
            if (!(R & 1)) res = max(res, seg[R--]);
            L >>= 1; R >>= 1;
        }
        return res;
    };

    update_value(0, 0);               // can start from height 0 only

    int best = 0;
    for (int i = 0; i < N; ++i) {
        int prevBest = query_suffix(a[i] - M);
        if (prevBest == NEG) continue; // unreachable as first kept pole
        int dp = prevBest + 1;
        best = max(best, dp);
        update_value(a[i], dp);
    }

    cout << (N - best) << "\n";
    return 0;
}

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