Submission #1123174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123174		crafticat	The short shank; Redemption (BOI21_prison)	C++20	35 / 100	2100 ms	121092 KiB

prison

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for (ll i = j;i < n;i++)

using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
constexpr ll INF = 1e9 + 7;
using pi = pair<ll,ll>;

ll T;

struct Seg {
    Seg *left = nullptr, *right = nullptr;
    ll l, r, mid;
    pair<double, int> v = {-INF, -INF};
    ll lazy = 0;

    ~Seg() {
        delete left;
        delete right;
    }

    void push() {
        if (lazy == 0) return;
        if (r -l >1) {
            left->lazy += lazy;
            right->lazy += lazy;
        }
        v.first += lazy;
        lazy = 0;
    }

    Seg(ll l ,ll r) : l(l), r(r), mid((l + r) / 2) {
        if (r -l > 1) {
            left = new Seg(l, mid);
            right = new Seg(mid, r);
        }
    }

    void add(ll a, ll b, ll u) {
        push();

        if (b <= l || a >= r) return;
        if (a <= l && b >= r) {
            lazy += u;
            push();
            return;
        }

        left->add(a, b, u);
        right->add(a,b,u);
        v = max(left->v, right->v);
    }
    void update(ll x, pair<double, int> u) {
        push();
        if (r - l <= 1) {
            v = max(v, u);
            return;
        }

        if (x < mid)
            left->update(x,u);
        else
            right->update(x,u);
        v = max(left->v, right->v);
    }
};

V<vi> createSeg; // imd
V<vi> remSeg; // At end

vi computeRightMost(vi arr) {
    multiset<ll> v;
    vi res(arr.size() + 1);

    FOR(i, 1, arr.size() + 1) {
        for (auto v2 : createSeg[i - 1])
            v.insert(v2);

        ll rightMost = v.empty() ? -1 : *v.rbegin(); // Right most is alright (not inc)
        res[i] = rightMost;

        for (auto v2 : remSeg[i - 1]) {
            v.erase(v.find(v2));
        }
    }
    return res;
}

pair<double, int> solve(const vi &arr, double p, const vi &rL) {
    Seg* segs;
    segs = new Seg(0, arr.size() + 1);
    segs->update(0, {0,0});

    FOR(i, 1, arr.size() + 1) {
        ll rightMost = rL[i];

        pair<double, int> vR = segs->v;
        segs->update(i - 1, {vR.first + p, vR.second + 1});

        segs->add(rightMost + 1, i, 1);
    }

    auto r = segs->v;
    delete segs;
    return r;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll n, k; cin >> n >> k >> T;
    vi arr(n);
    createSeg.resize(n + 1);
    remSeg.resize(n + 1);
    F0R(i, n)
        cin >> arr[i];

    F0R(i, n) {
        ll next = T - arr[i];
        if (next < 0) continue;
        createSeg[i].push_back(i);
        remSeg[min(i + next, n)].push_back(i);
    }
    vi rm = computeRightMost(arr);

    double l = -INF * 3, r = INF * 3;
    double ep = 0.00001;
    while (r > l) {
        double mid = l + (r - l + ep) / 2;
        if (solve(arr, mid, rm).second >= k) {
            r = mid - ep;
        } else {
            l = mid;
        }
    }

    cout << int(round(n - solve(arr, l, rm).first + k * l));

    return 0;
}

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