Submission #560619

#	Time	Username	Problem	Language	Result	Execution time	Memory
560619		Ooops_sorry	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1929 ms	300220 KiB

prison

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 2e6 + 10;
vector<int> g[N], used(N), mas;

struct SegTree {
    vector<int> t;
    int n;
    SegTree(int n_) {
        n = n_;
        t.resize(2 * n, -1);
    }
    void upd(int i, int val) {
        i += n;
        t[i] = max(t[i], val);
        for (; i > 1; i /= 2) {
            t[i / 2] = max(t[i], t[i ^ 1]);
        }
    }
    int get(int l, int r) {
        l += n, r += n + 1;
        int ans = -1;
        while (l < r) {
            if (l & 1) {
                ans = max(ans, t[l++]);
            }
            if (r & 1) {
                ans = max(ans, t[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
};

int dfs(int v) {
    used[v] = 1;
    if (g[v].size() == 0) {
        return 1;
    }
    vector<int> arr;
    int now = -1;
    for (auto to : g[v]) {
        int nw = dfs(to);
        if (nw > now) {
            if (now != -1) mas.pb(now);
            now = nw;
        } else {
            mas.pb(nw);
        }
    }
    return now + 1;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, d, T, ans = 0;
    cin >> n >> d >> T;
    vector<int> t(n), go(n, -1), u;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
        u.pb(t[i] - i);
        u.pb(T - i);
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    SegTree st((int)u.size());
    for (int i = 0; i < n; i++) {
        if (t[i] > T) {
            int j = lower_bound(u.begin(), u.end(), T - i) - u.begin();
            int pos = st.get(0, j);
            if (pos != -1) {
                go[i] = pos;
                ans++;
            }
        } else {
            ans++;
        }
        int j = lower_bound(u.begin(), u.end(), t[i] - i) - u.begin();
        st.upd(j, i);
    }
    deque<pair<int,int>> q;
    for (int i = n - 1; i >= 0; i--) {
        while (q.size() > 0 && q.back().first > i) {
            q.pop_back();
        }
        if (go[i] != -1) {
            if (q.size() > 0) {
                g[q.back().second].pb(i);
            }
            q.pb({go[i], i});
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (!used[i]) {
            int val = dfs(i);
            mas.pb(val);
        }
    }
    sort(mas.rbegin(), mas.rend());
    for (int i = 0; i < min((int)mas.size(), d); i++) {
        ans -= mas[i];
    }
    cout << ans << endl;
    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