제출 #1216555

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

triusis

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

struct SegTree {
    int n;
    vector<int> st;
    SegTree(int _n): n(_n), st(4*n, 0) {}
    void update(int p, int val) { update(1, 0, n-1, p, val); }
    int query(int L, int R) { 
        if (L > R) return 0;
        return query(1, 0, n-1, L, R); 
    }
  private:
    void update(int node, int l, int r, int p, int val) {
        if (l == r) {
            st[node] = max(st[node], val);
        } else {
            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 0;
        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;
    long long M;
    cin >> N >> M;
    vector<long long> a(N);
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }

    // Coordinate-compress heights
    vector<long long> comp = a;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    auto getIdx = [&](long long x){
        return int(lower_bound(comp.begin(), comp.end(), x) - comp.begin());
    };

    int C = comp.size();
    SegTree st(C);

    int best = 0;
    for(int i = 0; i < N; i++){
        long long h = a[i];
        // Find minimum height h0 so that h - h0 <= M  =>  h0 >= h - M
        long long minH = h - M;
        int left = int(lower_bound(comp.begin(), comp.end(), minH) - comp.begin());
        int right = C - 1;
        // DP transition: best previous + 1
        int prevBest = st.query(left, right);
        int dp = prevBest + 1;
        // Also allow starting from ground (height 0) if h <= M
        if (h <= M) dp = max(dp, 1);
        best = max(best, dp);

        // update segtree at position of h
        int pos = getIdx(h);
        st.update(pos, dp);
    }

    // We can keep 'best' poles unmodified. The rest must be modified.
    cout << (N - best) << "\n";
    return 0;
}

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