Submission #674505

#	Time	Username	Problem	Language	Result	Execution time	Memory
674505		stanislavpolyn	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1286 ms	447272 KiB

prison

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); i++)
#define rf(i, a, b) for (int i = (a); i >= (b); i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e6 + 5;

int n, d, T;
int a[N];

ve<int> del[N];
ve<int> add[N];
set<int> s;
int p[N];
int pi[N];
ve<int> g[N];
int total;
bool alive[N];
bool mark[N];

pii dp[N];
int dep[N];

void dfs(int v) {
    pii mx = {int(-1e9), -1};
    fe (to, g[v]) {
        dep[to] = dep[v] + 1;
        dfs(to);
        umx(mx, dp[to]);
    }
    umx(mx, mp(dep[v], v));
    dp[v] = mx;
}

set<pii> q;

int main() {
#ifndef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    cin >> n >> d >> T;

    fr (i, 1, n) {
        cin >> a[i];
    }

    {
        fr (i, 1, n) {
            fe (cur, del[i]) s.erase(cur);
            if (a[i] <= T) {
                s.insert(i);
                if (i + T - a[i] + 1 <= n) {
                    del[i + T - a[i] + 1].pb(i);
                }
            }
            p[i] = sz(s) ? *s.rbegin() : -1;
        }
    }

    fr (i, 1, n) {
        del[i].clear();
        add[i].clear();
    }

    fr (i, 1, n) {
        if (p[i] == -1) continue;

        if (p[i] + 1 <= i) {
            add[p[i] + 1].pb(i);
            del[i].pb(i);
            // cout << p[i] + 1 << " " << i - 1 << " " << i << "\n";
        }
    }

    s.clear();
    fr (i, 1, n) {
        fe (x, add[i]) s.insert(x);
        fe (x, del[i]) s.erase(x);

        pi[i] = sz(s) ? *s.begin() : 0;
    }

    // fr (i, 1, n) {
    //     cout << p[i] << " ";
    // }
    // cout << "\n";

    // fr (i, 1, n) {
    //     cout << pi[i] << " ";
    // }
    // cout << "\n";

    fr (i, 1, n) {
        if (p[i] != -1) total++;
        if (p[i] == i || p[i] == -1) continue;

        alive[i] = 1;

        // cout << "vertex: " << i << "\n";

        if (pi[i]) {
            g[pi[i]].pb(i);
            // cout << pi[i] << " " << i << "\n";
        }
    }

    // cout << total << "\n";

    fr (i, 1, n) {
        if (alive[i] && !pi[i]) {
            dfs(i);
            q.insert(dp[i]);
        }
    }

    while (sz(q) && d > 0) {
        d--;
        int v = (--q.end())->se;
        q.erase(--q.end());

        while (!mark[v]) {
            mark[v] = 1;
            fe (to, g[v]) {
                if (!mark[to]) {
                    q.insert({dp[to].fi - dep[v] - 1, dp[to].se});
                }
            }

            if (!pi[v]) break;
            v = pi[v];
        }
    }

    fr (i, 1, n) {
        if (mark[i]) {
            total--;
        }
    }

    cout << total << "\n";

    // fr (i, 1, n) {
    //     cout << pi[i] << " ";
    // }
    // cout << "\n";

    return 0;
}

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