Submission #646052

#	Time	Username	Problem	Language	Result	Execution time	Memory
646052		alextodoran	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1314 ms	415448 KiB

prison

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N_MAX = 2000000;

int N, K, T;
int start[N_MAX + 2];

int spread[N_MAX + 2];
vector <int> endSpread[N_MAX + 2];
int maxTrigger[N_MAX + 2];

int parent[N_MAX + 2];
vector <int> sons[N_MAX + 2];

int depth[N_MAX + 2];

int M;
int order[N_MAX + 2];
int L[N_MAX + 2], R[N_MAX + 2];

void dfs (int u) {
    order[++M] = u;
    L[u] = R[u] = M;
    for (int v : sons[u]) {
        depth[v] = depth[u] + 1;
        dfs(v);
        R[u] = R[v];
    }
}

bool active[N_MAX + 2];

struct SegInfo {
    int maxVal;
    int maxID;
    int lazy;
};
SegInfo operator + (const SegInfo &x, const SegInfo &y) {
    SegInfo z;
    if (x.maxVal > y.maxVal) {
        z = x;
    } else {
        z = y;
    }
    z.lazy = 0;
    return z;
}
void operator += (SegInfo &x, const int &y) {
    x.maxVal += y;
    x.lazy += y;
}

SegInfo segTree[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        segTree[node] = SegInfo{depth[order[l]], l, 0};
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    build(left, l, mid);
    build(right, mid + 1, r);
    segTree[node] = segTree[left] + segTree[right];
}
void build () {
    build(1, 1, M);
}
void update (int node, int l, int r, int ul, int ur) {
    if (ul <= l && r <= ur) {
        segTree[node] += -1;
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    segTree[left] += segTree[node].lazy;
    segTree[right] += segTree[node].lazy;
    if (ul <= mid) {
        update(left, l, mid, ul, ur);
    }
    if (mid + 1 <= ur) {
        update(right, mid + 1, r, ul, ur);
    }
    segTree[node] = segTree[left] + segTree[right];
}
void update (int ul, int ur) {
    update(1, 1, M, ul, ur);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> T;
    for (int i = 1; i <= N; i++) {
        cin >> start[i];
        spread[i] = max(i - 1, min(N, i + (T - start[i])));
        if (spread[i] < N) {
            endSpread[spread[i]].push_back(i);
        }
    }
    set <int> triggers;
    for (int i = 1; i <= N; i++) {
        if (start[i] <= T) {
            triggers.insert(i);
        }
        maxTrigger[i] = (triggers.empty() == false ? *triggers.rbegin() : 0);
        for (int j : endSpread[i]) {
            triggers.erase(j);
        }
    }

    int answer = 0;
    vector <int> st;
    for (int i = N; i >= 1; i--) {
        while (st.empty() == false && maxTrigger[st.back()] >= i) {
            st.pop_back();
        }
        parent[i] = (st.empty() == false ? st.back() : 0);
        if (maxTrigger[i] > 0) {
            answer++;
            if (maxTrigger[i] < i) {
                active[i] = true;
                st.push_back(i);
            }
        }
    }
    for (int u = 1; u <= N; u++) {
        if (active[u] == true && parent[u] != 0) {
            sons[parent[u]].push_back(u);
        }
    }
    for (int u = 1; u <= N; u++) {
        if (active[u] == true && parent[u] == 0) {
            depth[u] = 1;
            dfs(u);
        }
    }
    if (M != 0) {
        build();
        while (K--) {
            int u = order[segTree[1].maxID];
            int v = u;
            while (active[v] == true) {
                answer--;
                active[v] = false;
                update(L[v], R[v]);
                v = parent[v];
            }
        }
    }
    cout << answer << "\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