Submission #644883

#	Time	Username	Problem	Language	Result	Execution time	Memory
644883		alextodoran	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	26 ms	47328 KiB

prison

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 2000000;
const double EPS = 0.00001;

int N, K, T;
int start[N_MAX + 2];

int spread[N_MAX + 2];
vector <int> endSpread[N_MAX + 2];
int maxTrigger[N_MAX + 2];

double segMin[N_MAX * 4 + 2];
int segMinID[N_MAX * 4 + 2];
double segLazy[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    segMin[node] = 0;
    segMinID[node] = l;
    segLazy[node] = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    build(left, l, mid);
    build(right, mid + 1, r);
}
void build () {
    build(1, 0, N);
}
void update (int node, int l, int r, int ul, int ur, double uval) {
    if (ul <= l && r <= ur) {
        segMin[node] += uval;
        segLazy[node] += uval;
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    segMin[left] += segLazy[node]; segLazy[left] += segLazy[node];
    segMin[right] += segLazy[node]; segLazy[right] += segLazy[node];
    segLazy[node] = 0;
    if (ul <= mid) {
        update(left, l, mid, ul, ur, uval);
    }
    if (mid + 1 <= ur) {
        update(right, mid + 1, r, ul, ur, uval);
    }
    segMin[node] = min(segMin[left], segMin[right]);
    segMinID[node] = (segMin[node] == segMin[left] ? segMinID[left] : segMinID[right]);
}
void update (int ul, int ur, double uval) {
    update(1, 0, N, ul, ur, uval);
}
pair <double, int> query (int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return make_pair(segMin[node], segMinID[node]);
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    segMin[left] += segLazy[node]; segLazy[left] += segLazy[node];
    segMin[right] += segLazy[node]; segLazy[right] += segLazy[node];
    segLazy[node] = 0;
    double queryMin = INT_MAX; int queryMinID = 0;
    if (ql <= mid) {
        tie(queryMin, queryMinID) = query(left, l, mid, ql, qr);
    }
    if (mid + 1 <= qr) {
        double rightMin; int rightMinID;
        tie(rightMin, rightMinID) = query(right, mid + 1, r, ql, qr);
        if (rightMin < queryMin) {
            queryMin = rightMin;
            queryMinID = rightMinID;
        }
    }
    return make_pair(queryMin, queryMinID);
}
pair <double, int> query (int ql, int qr) {
    return query(1, 0, N, ql, qr);
}

double cutCost;
double minPref[N_MAX + 2];
int cutsPref[N_MAX + 2];

void solve () {
    build();
    double cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (maxTrigger[i] > 0) {
            cnt++;
            update(0, maxTrigger[i] - 1, + 1);
        }
        double prefMin; int prefMinID;
        tie(prefMin, prefMinID) = query(0, i - 1);
        minPref[i] = prefMin + cutCost;
        cutsPref[i] = cutsPref[prefMinID] + 1;
        if (cnt < minPref[i]) {
            minPref[i] = cnt;
            cutsPref[i] = 0;
        }
        update(i, i, minPref[i]);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(6);

    cin >> N >> K >> T;
    for (int i = 1; i <= N; i++) {
        cin >> start[i];
        spread[i] = max(i - 1, min(N, i + (T - start[i])));
        if (spread[i] < N) {
            endSpread[spread[i]].push_back(i);
        }
    }
    set <int> triggers;
    for (int i = 1; i <= N; i++) {
        if (start[i] <= T) {
            triggers.insert(i);
        }
        maxTrigger[i] = (triggers.empty() == false ? *triggers.rbegin() : 0);
        for (int j : endSpread[i]) {
            triggers.erase(j);
        }
    }

    double l = 0, r = N + 1;
    int iter = 30;
    while (iter--) {
        cutCost = (l + r) / 2;
        solve();
        if (cutsPref[N] > K) {
            l = cutCost + EPS;
        } else {
            r = cutCost;
        }
    }
    cutCost = r;
    solve();
    cout << (int) round(minPref[N] - cutsPref[N] * cutCost) << "\n";

    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