제출 #720835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720835		Johann	The short shank; Redemption (BOI21_prison)	C++14	55 / 100	2066 ms	10620 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()

int N, D, T;
vi P;

struct segtree
{
    int size;
    vi arr;
    void init(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        arr.assign(2 * size, 0);
    }
    int query(int l, int r) { return query(l, r, 1, 0, size); }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
            return arr[x];
        if (r <= lx || rx <= l)
            return 0;
        int m = (lx + rx) / 2;
        return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx);
    }
    void block(int l, int r) { block(l, r, 1, 0, size); }
    void block(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r && rx - lx == 1)
        {
            arr[x] = 1;
            return;
        }
        if (r <= lx || rx <= l || arr[x] == rx - lx)
            return;
        int m = (lx + rx) / 2;
        block(l, r, 2 * x, lx, m);
        block(l, r, 2 * x + 1, m, rx);
        arr[x] = arr[2 * x] + arr[2 * x + 1];
    }
};

pii solve()
{
    vi pref(N + 1, 0); // number of protestants in range [0, i)
    int border = -1;
    for (int i = 0; i < N; ++i)
    {
        border = max(border, i + T - P[i]);
        pref[i + 1] = pref[i];
        if (i <= border)
            pref[i + 1] += 1;
    }

    vi suff(N + 1, 0); // number of protestants in range [i, N-1]
    segtree seg;
    seg.init(N);
    for (int i = N - 1; i >= 0; --i)
    {
        if (P[i] <= T)
            seg.block(i, i + T - P[i] + 1);
        suff[i] = seg.query(0, N);
    }
    assert(pref[N] == suff[0]);

    // ans = { cnt, last prisoner befor matresse}
    pii ans = {pref[N], N - 1}; // Matresse after N-1 and bevor N, full stuff
    for (int i = 0; i < N; ++i)
    {
        ans = min(ans, {suff[i] + pref[i], i - 1});
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> D >> T;
    D = min(D, N);
    P.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i];

    pii ans;
    for (int d = 0; d < D; ++d)
    {
        ans = solve();
        for (int i = 0; i <= ans.second; ++i)
            P[i] = max(P[i], i + T - ans.second);
    }
    cout << ans.first << endl;

    return 0;
}

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