제출 #1271965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271965		ceceg	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	3 ms	580 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];

    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, 0);

    auto upd = [&](int pos, int v) {
        pos = lower_bound(vals.begin(), vals.end(), (long long)pos) - vals.begin(); // not used
    };

    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);
        for (p >>= 1; p; p >>= 1) seg[p] = max(seg[p<<1], seg[p<<1|1]);
    };

    auto query_suffix = [&](long long t) {
        int l = int(lower_bound(vals.begin(), vals.end(), t) - vals.begin());
        if (l >= K) return 0;
        int L = l + SZ, R = SZ + K - 1;
        int res = 0;
        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);

    int best = 0;
    for (int i = 0; i < N; ++i) {
        long long need = a[i] - M;
        int dp = 1 + query_suffix(need);
        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