Submission #722405

#	Time	Username	Problem	Language	Result	Execution time	Memory
722405		Johann	The short shank; Redemption (BOI21_prison)	C++14	10 / 100	447 ms	84812 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()
#define all(x) (x).begin(), (x).end()

int N, D, T;
vi P;

vi ranges; // [ranges[i], i) exclusive: where a matresse has to go to protect position i
vi protest;

struct segtree
{
    int size;
    vi arr;
    vvi contains;
    void init(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        arr.assign(2 * size, 0);
        contains.resize(2 * size);
    }
    void add(int i) { add(ranges[i], i, i, 1, 0, size); }
    void add(int l, int r, int i, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            contains[x].push_back(i);
            ++arr[x];
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        add(l, r, i, 2 * x, lx, m);
        add(l, r, i, 2 * x + 1, m, rx);
        arr[x] = max(arr[2 * x], arr[2 * x + 1]) + sz(contains[x]);
    }
    void remove(int l, int r, int i, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            --arr[x];
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        remove(l, r, i, 2 * x, lx, m);
        remove(l, r, i, 2 * x + 1, m, rx);
        arr[x] = max(arr[2 * x], arr[2 * x + 1]) + sz(contains[x]);
    }
    void placeMatresse()
    {
        binSearch(1, 0, size);
    }
    void binSearch(int x, int lx, int rx)
    {
        while (!contains[x].empty())
        {
            int i = contains[x].back();
            if (ranges[i] != -1)
            {
                protest[i] = false;
                remove(ranges[i], i, i, 1, 0, size);
                ranges[i] = -1;
            }
            contains[x].pop_back();
        }
        if (rx - lx == 1 || max(arr[2 * x], arr[2 * x + 1]) == 0)
            return;
        int m = (lx + rx) / 2;
        if (arr[2 * x] >= arr[2 * x + 1])
            binSearch(2 * x, lx, m);
        else
            binSearch(2 * x + 1, m, rx);
    }
};

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];

    protest.assign(N, false);
    ranges.assign(N, -1);
    priority_queue<pii> blockers; // which range is blocked [i, j] inclusive
    segtree seg;
    seg.init(N);
    for (int i = 0; i < N; ++i)
    {
        if (P[i] <= T)
        {
            protest[i] = true;
            blockers.push({i, min(i + T - P[i], N)});
        }
        else
        {
            while (!blockers.empty() && blockers.top().second < i)
                blockers.pop();
            if (!blockers.empty())
            {
                protest[i] = true;
                ranges[i] = blockers.top().first;
                seg.add(i);
            }
        }
    }

    for (int foo = 0; foo < D; ++foo)
        seg.placeMatresse();

    cout << accumulate(all(protest), 0) << endl;

    return 0;
}

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