제출 #427396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427396		keko37	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	32 ms	47344 KiB

prison

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 2000005;
const llint INF = 1000000000000000000LL;

int n, k, T, ofs = 1;
int t[MAXN], lim[MAXN], add[MAXN];
llint mx[75005 * 4], br[75005 * 4], prop[75005 * 4];
pi dp[MAXN];
set <int> st;
vector <int> v[MAXN];

void build () {
    for (int i = 1; i <= n; i++) {
        int j = i + T - t[i];
        if (i <= j) {
            st.insert(i);
            if (j + 1 <= n) v[j + 1].push_back(i);
        }
        for (auto x : v[i]) {
            st.erase(x);
        }
        if (!st.empty()) {
            lim[i] = *st.rbegin();
            if (lim[i] < i) add[lim[i]]++;
        } else {
            lim[i] = 1e9;
        }
    }
}

void upd (int x, pi novi) {
    x += ofs;
    mx[x] = novi.first;
    br[x] = novi.first;
    x /= 2;
    while (x > 0) {
        pi lef = {mx[2 * x] + prop[2 * x], br[2 * x]};
        pi rig = {mx[2 * x + 1] + prop[2 * x + 1], br[2 * x + 1]};
        pi res = max(lef, rig);
        mx[x] = res.first;
        br[x] = res.second;
        x /= 2;
    }
}

pi update (int x, int from, int to, int lo, int hi, int val) {
    if (from <= lo && hi <= to) {
        prop[x] += val;
        return {mx[x] + prop[x], br[x]};
    }
    if (to < lo || hi < from) return {-INF, -INF};
    pi lef = update(2 * x, from, to, lo, (lo + hi) / 2, val);
    pi rig = update(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, val);
    pi res = max(lef, rig);
    mx[x] = res.first;
    br[x] = res.second;
    return {mx[x] + prop[x], br[x]};
}

pi calc (llint cost) {
    for (int i = 0; i < 2 * ofs; i++) {
        mx[i] = -INF; br[i] = -INF;
        prop[i] = 0;
    }
    upd(0, {0, 0});
    pi res = {0, 0};
    int curr = 0;
    for (int i = 1; i <= n; i++) {
        curr += add[i];
        if (lim[i] < i) {
            update(1, lim[i], i - 1, 0, ofs - 1, 1);
            curr--;
        }
        dp[i] = {mx[1] + curr - cost, br[1]};
        upd(i, {dp[i].first - curr, dp[i].second});
        res = max(res, dp[i]);
    }
    return res;
}

llint bs () {
    llint lo = 0, hi = 1e9;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        pi res = calc(mid);
        if (res.second > k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    pi res = calc(lo);
    return res.first + lo * k;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> T;
    while (ofs < n + 1) ofs *= 2;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    build();
    cout << n - bs();
    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