Submission #1228891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228891		ghgcdc	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	4 ms	3656 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
const int N = 2*1e5+1;
const int M = N * 4;
int tr[M],n,k;
long long h[N], c[N * 2],m;
void upd(int node, int l, int r, int idx, int val){
    if(l == r){
        tr[node] = max(tr[node], val);
        return;
    }
    int mid =(l + r) / 2;
    if(idx <= mid) upd(node * 2, l, mid, idx, val);
    else upd(node * 2 + 1, mid + 1, r, idx, val);
    tr[node] = max(tr[node * 2], tr[node * 2 + 1]);
}
int qry(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return 0;
    if(ql <= l && r <= qr) return tr[node];
    int mid =(l + r) / 2;
    return max(qry(node * 2, l, mid, ql, qr), qry(node * 2 + 1, mid + 1, r, ql, qr));
}
int lb(long long v){
    int l = 0, r = k - 1, ans = k;
    while(l <= r){
        int mid =(l + r) / 2;
        if(c[mid] >= v){
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ans;
}
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 = 0;
    for(int i = 0; i < sz; ++i)if(i == 0 || c[i] != c[i - 1])c[k++] = c[i];
    memset(tr, 0, sizeof(tr));
    int res = 0;
    for(int i = 0; i <= n; ++i){
        int l = lb(h[i] - m),cur = lb(h[i]),dp = qry(1, 0, k - 1, l, k - 1);
        if(dp > 0 || i == 0){
            dp++;
            res = max(res, dp);
            upd(1, 0, k - 1, cur, dp);
        }
    }
    cout<<n -(res - 1)<<'\n';
    return 0;
}

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