Submission #538266

#	Time	Username	Problem	Language	Result	Execution time	Memory
538266		Stickfish	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	122 ms	88304 KiB

prison

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 2e6 + 123;
vector<int> edg[MAXN];
int rt[MAXN];

int init(int n) {
    int t;
    cin >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<pair<int, int>> stck;
    vector<int> vl(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        stck.push_back({a[i], i});
        while (stck.size() && t - stck.back().first < i - stck.back().second)
            stck.pop_back();
        if (stck.size()) {
            vl[i] = stck.back().second;
        } else {
            ++ans;
            vl[i] = n + 1;
        }
    }
    //for (int i = 0; i < n; ++i)
        //cout << vl[i] << ' ';
    //cout << endl;
    vector<int> way;
    for (int i = n - 1; i >= 0; --i) {
        while (way.size() && vl[way.back()] > i) {
            way.pop_back();
        }
        if (vl[i] >= i) {
            rt[i] = -1;
            continue;
        }
        if (vl[i] < i && way.size()) {
            rt[i] = way.back();
            edg[way.back()].push_back(i);
        } else {
            rt[i] = 0;
            edg[0].push_back(i);
        }
        way.push_back(i);
    }
    //for (int i = 0; i < n; ++i) {
        //cout << rt[i] << ' ';
    //}
    //cout << endl;
    return ans;
}

vector<int>* unite(vector<int>* a, vector<int>* b, int d) {
    int n = a->size();
    if ((*a)[0]) {
        for (int i = 1; i < n; ++i)
            (*a)[i] += (*a)[0];
        (*a)[0] = 0;
    }
    int m = b->size();
    if ((*b)[0]) {
        for (int i = 1; i < m; ++i)
            (*b)[i] += (*b)[0];
        (*b)[0] = 0;
    }
    if (n < m)
        swap(a, b);
    int sz = min(d + 1, n + m - 1);
    a->resize(sz);
    for (int i = sz - 1; i > 0; --i) {
        for (int j = 0; j < m && j <= i; ++j) {
            (*a)[i] = max((*a)[i], (*a)[i - j] + (*b)[j]);
        }
    }
    delete b;
    return a;
}

vector<int>* dfs(int v, int d) {
    if (edg[v].empty()) {
        vector<int>* ans = new vector<int>(2);
        (*ans)[1] = 1;
        return ans;
    }
    vector<int>* ans = nullptr;
    for (auto u : edg[v]) {
        if (!ans) {
            ans = dfs(u, d);
        } else {
            ans = unite(ans, dfs(u, d), d);
        }
    }
    ++(*ans)[0];
    //cout << v << ": ";
    //for (auto x : ans)
        //cout << x << ' ';
    //cout << endl;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, d;
    cin >> n >> d;
    int neut = init(n);
    vector<int>* vvv = dfs(0, d);
    int ans = vvv->front() + vvv->back();
    //cout << "(" << ans << ' ' << neut << ") " << endl;
    cout << n - ans - neut + 1 << endl;
}

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