Submission #729099

#	Time	Username	Problem	Language	Result	Execution time	Memory
729099		_martynas	The short shank; Redemption (BOI21_prison)	C++11	100 / 100	516 ms	58524 KiB

prison

#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define all(a) (a).begin(), (a).end()

const int MXN = 2e6+5;

int n, d, t;
int T[MXN];
int always = 0, perchance = 0, preventable = 0;
bool maybe[MXN];
int covered_by[MXN], par[MXN], H[MXN], who[MXN];
bool visited[MXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> t;
    for(int i = 1; i <= n; i++) cin >> T[i];
    stack<int> st;
    for(int i = n; i >= 1; i--) {
        while(!st.empty() && st.top()-i <= t-T[i]) {
            covered_by[st.top()] = i;
            maybe[st.top()] = true;
            perchance++;
            st.pop();
        }
        if(T[i] > t) st.push(i);
        else always++;
    }
    stack<int> open, closing;
    for(int i = n; i >= 1; i--) {
        while(!closing.empty() && closing.top() == i) open.pop(), closing.pop();
        if(!maybe[i]) continue;
        if(!open.empty()) {
            par[i] = open.top();
        }
        open.push(i);
        closing.push(covered_by[i]);
    }
    vector<int> order;
    for(int i = 1; i <= n; i++) {
        if(!maybe[i]) continue;
        if(par[i] != 0) {
            if(H[par[i]] < H[i]+1) {
                H[par[i]] = H[i]+1;
                who[par[i]] = i;
            }
        }
        order.PB(i);
    }
    sort(all(order), [&](int i, int j) {
         return H[i] > H[j];
    });
    for(int i : order) {
        if(visited[i]) continue;
        if(!d) break;
        int j = i;
        while(j) {
            preventable++;
            visited[j] = true;
            j = who[j];
        }
        d--;
    }
    cout << always+(perchance-preventable) << "\n";
    return 0;
}
/*
1 1 1
2


*/

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