Submission #847350

#	Time	Username	Problem	Language	Result	Execution time	Memory
847350		MinaRagy06	The short shank; Redemption (BOI21_prison)	C++17	70 / 100	2089 ms	19028 KiB

prison

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define md  ((l + r) >> 1)
using namespace std;
typedef int64_t ll;
 
int n, m, t;
const int N = 500'005;
struct node {
    int lazy;
    array<int, 2> mn;
    node() {
        lazy = 0;
        mn = {int(1e9), int(1e9)};
    }
    node(array<int, 2> _mn) {
        lazy = 0;
        mn = _mn;
    }
    friend node operator+(const node &l, const node &r) {
        node ret;
        ret.mn = min(l.mn, r.mn);
        return ret;
    }
};
node seg[1 << (__lg(N - 1) + 2)];
void process(int i, int l, int r) {
    if (l != r) {
        for (auto c : {i << 1, i << 1 | 1}) {
            seg[c].lazy += seg[i].lazy;
        }
    }
    seg[i].mn[0] += seg[i].lazy;
    seg[i].lazy = 0;
}
void upd(int i, int l, int r, int s, int e, int v) {
    process(i, l, r);
    if (s <= l && r <= e) {
        seg[i].lazy += v;
        process(i, l, r);
        return;
    }
    if (r < s || e < l) {
        return;
    }
    upd(i << 1, l, md, s, e, v);
    upd(i << 1 | 1, md + 1, r, s, e, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void upd2(int i, int l, int r, int x, array<int, 2> v) {
    process(i, l, r);
    if (l == x && x == r) {
        seg[i] = v;
        return;
    }
    if (r < x || x < l) {
        return;
    }
    upd2(i << 1, l, md, x, v);
    upd2(i << 1 | 1, md + 1, r, x, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
    process(i, l, r);
    if (s <= l && r <= e) {
        return seg[i];
    }
    if (r < s || e < l) {
        return node();
    }
    return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
void update(int s, int e, int v) {
    if (s > e) return;
    upd(1, 0, n - 1, s, e, v);
}
void update(int x, array<int, 2> v) {
    if (x < 0) return;
    upd2(1, 0, n - 1, x, v);
}
array<int, 2> query(int s, int e) {
    return get(1, 0, n - 1, s, e).mn;
}
int a[N];
array<int, 2> dp[N];
array<int, 2> calc(int c) {
    for (int i = 0; i < n; i++) {
        dp[i] = {int(1e9), int(1e9)};
    }
    stack<int> s;
    dp[n] = {0, 0};
    update(n - 1, dp[n]);
    s.push(n);
    for (int i = n - 1; i >= 0; i--) {
        /*int cur = 1e9, ctr = 0;
        for (int k = i; k < n; k++) {
            cur = min(cur + 1, a[k]);
            ctr += (cur <= t);
            dp[i] = min(dp[i], {dp[k + 1][0] + ctr, dp[k + 1][1]});
        }*/
//        cout << i << ": ";
        int lst = i;
        while (a[i] + s.top() - i <= a[s.top()]) {
            int k = s.top();
            s.pop();
            int eni = t + i - a[i];
            int enk = t + k - a[k];
            enk++;
//            cout << enk << ' ' << eni << ' ' << k << ' ' << a[k] << '\n';
            if (enk > eni || enk > s.top() - 1 || eni < lst + 1) continue;
            eni = max(lst + 1, min(s.top() - 1, eni));
            enk = max(lst + 1, min(s.top() - 1, enk));
            for (int j = enk; j <= eni; j++) {
                update(j, j, j - enk + 1);
            }
            lst = eni;
            update(eni + 1, n - 1, eni - enk + 1);
        }
//        cout << '\n';
        if (a[i] <= t) {
            update(i, n - 1, 1);
        }
        s.push(i);
        dp[i] = query(i, n - 1);
        dp[i][0] += c, dp[i][1]++;
        update(i - 1, dp[i]);
    }
//    for (int i = 0; i <= n; i++) {
//        cout << dp[i][0] << ' ';
//    }
//    cout << '\n';
    return {dp[0][0], dp[0][1]};
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    a[n] = -1;
    m++;
    int l = 0, r = n;
    while (l <= r) {
        array<int, 2> v = calc(md);
//        cout << md << ' ' << v[0] << ' ' << v[1] << '\n';
        if (v[1] <= m) {
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    cout << calc(l)[0] - m * l << '\n';
    return 0;
}

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