제출 #1228966

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

triusis

#include<bits/stdc++.h>
using namespace std;
const int N = 2*1e5 + 1,M = 4*1e5+2, S = 8*1e5+5;
int t[S],n,k;
long long h[N],c[M],m;
void u(int p, int l, int r, int i, int v){
    if(l == r){
        t[p] = max(t[p], v);
        return;
    }
    int mid =(l + r)>>1;
    if(i <= mid) u(p * 2, l, mid, i, v);
    else u(p * 2 + 1, mid + 1, r, i, v);
    t[p] = max(t[p * 2], t[p * 2 + 1]);
}
int q(int p, int l, int r, int L, int R){
    if(R < l || r < L) return 0;
    if(L <= l && r <= R) return t[p];
    int mid =(l + r)>>1;
    return max(q(p * 2, l, mid, L, R), q(p * 2 + 1, mid + 1, r, L, R));
}
int lb(long long v){
    return lower_bound(c, c + k, v) - c;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    h[0] = 0;
    for(int i = 1; i <= n; ++i) cin>>h[i];
    int sz = 0;
    for(int i = 0; i <= n; ++i){
        c[sz++] = h[i];
        c[sz++] = h[i] - m;
    }
    sort(c, c + sz);
    k = unique(c, c + sz) - c;
    memset(t, 0, sizeof(t));
    int r = 0;
    for(int i = 0; i <= n; ++i){
        int l = lb(h[i] - m),cur = lb(h[i]),dp = q(1, 0, k - 1, l, k - 1);
        if(dp > 0 || i == 0){
            dp++;
            r = max(r, dp);
            u(1, 0, k - 1, cur, dp);
        }
    }
    cout<<n -(r - 1)<<'\n';
    return 0;
}

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