제출 #668996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668996		mychecksedad	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	195 ms	12720 KiB

prison

/* 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);

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

    ans = 0;

    vector<bool> takeble(n + 1);

    for(int i = 1; i <= n; ++i){
        if(get(1, n, i, 1) > 0){
            ans++;
            takeble[i] = 1;
        }
    }

    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(takeble[i] && 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;
 
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20