Submission #668992

#TimeUsernameProblemLanguageResultExecution timeMemory
668992mychecksedadThe short shank; Redemption (BOI21_prison)C++17
0 / 100
112 ms8280 KiB
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e6+10, M = 5100, MOD = 1e9+7;


int n, d, a[N], T, ans, t[N*4];

void build(int l, int r, int k){
    if(l == r){
        t[k] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    t[k] = 0;
}

void update(int l, int r, int ql, int qr, int k, int val){
    if(l > qr || r < ql) return;
    if(ql <= l && r <= qr){
        t[k] = max(t[k], val);
        return;
    }
    int m = (l + r) >> 1;
    update(l, m, ql, qr, k<<1, val);
    update(m+1, r, ql, qr, k<<1|1, val);
}

int get(int l, int r, int p, int k){
    if(l == r){
        return t[k];
    }   
    int m = (l + r) >> 1;

    if(p <= m)
        return max(t[k], get(l, m, p, k<<1));

    return max(t[k], get(m + 1, r, p, k<<1|1));
}

void solve(){
    cin >> n >> d >> T;

    for(int i = 1; i <= n; ++i) cin >> a[i];

    build(1, n, 1);

    ans = n;

    for(int i = 1; i <= n; ++i){
        if(a[i] <= T){
            update(1, n, i, n, 1, i);
        }
    }

    vector<int> v(n + 1);

    for(int i = 1; i <= n; ++i){
        if(a[i] > T)
            v[get(1, n, i, 1)]++;
    }

    sort(v.begin() + 1, v.begin() + n + 1, greater<int>());

    for(int i = 1; i <= d; ++i){
        ans -= v[i];
    }

    cout << ans;
}




int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    solve();
    return 0;
 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...