Submission #1228972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228972		buixuia	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	6 ms	6728 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
const long long N = 2*1e5 + 1,M = 4*1e5+2, S = 8*1e5+5;
long long t[S],n,k;
long long h[N],c[M],m;
void u(long long p, long long l, long long r, long long i, long long v){
    if(l == r){
        t[p] = max(t[p], v);
        return;
    }
    long long 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]);
}
long long q(long long p, long long l, long long r, long long L, long long R){
    if(R < l || r < L) return 0;
    if(L <= l && r <= R) return t[p];
    long long mid =(l + r)>>1;
    return max(q(p * 2, l, mid, L, R), q(p * 2 + 1, mid + 1, r, L, R));
}
long long 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(long long i = 1; i <= n; ++i) cin>>h[i];
    long long sz = 0;
    for(long long 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));
    long long r = 0;
    for(long long i = 0; i <= n; ++i){
        long long 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