Submission #675887

#	Time	Username	Problem	Language	Result	Execution time	Memory
675887		ParsaS	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	249 ms	107088 KiB

prison

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5;
int n, D, T, t[N];
int lt[N], par[N], tim, tin[N], tout[N];
vector<int> adj[N];
vector<pair<int, int> > vec;
bool vis[N];
int seg[N << 2], mx[N << 2], lz[N << 2], h[N];

void dfs(int v) {
    tin[v] = tim++;
    vec.pb(mp(h[v], v));
    for (auto u : adj[v]) {
        h[u] = h[v] + 1;
        dfs(u);
    }
    tout[v] = tim - 1;
}
void build(int v = 1, int tl = 0, int tr = tim) {
    if (tl == tr) {
        seg[v] = vec[tl].se; 
        mx[v] = vec[tl].fi;
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1 | 1, mid + 1, tr);
    seg[v] = seg[v << 1];
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    if (h[seg[v << 1 | 1]] > h[seg[v << 1]])
        seg[v] = seg[v << 1 | 1];
}
void shift(int v, int tl, int tr) {
    mx[v] -= lz[v];
    if (tl < tr) {
        lz[v << 1] += lz[v];
        lz[v << 1 | 1] += lz[v];
    }
    lz[v] = 0;
}
void upd(int l, int r, int v = 1, int tl = 0, int tr = tim) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        lz[v]++;
        shift(v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, v << 1, tl, mid);
    upd(l, r, v << 1 | 1, mid + 1, tr);
    seg[v] = seg[v << 1];
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    if (mx[v] == mx[v << 1 | 1])
        seg[v] = seg[v << 1 | 1];
}
pair<int, int> query(int l, int r, int v = 1, int tl = 0, int tr = tim) {
    shift(v, tl, tr);
    pair<int, int> out(-1, n + 1);
    if (l > tr || r < tl)
        return mp(-1, n + 1);
    if (tl >= l && tr <= r)
        return mp(mx[v], seg[v]);
    int mid = (tl + tr) >> 1;
    pair<int, int> pl = query(l, r, v << 1, tl, mid);
    pair<int, int> pr = query(l, r, v << 1 | 1, mid + 1, tr);
    return pl > pr ? pl : pr;
}

void solve() {
    cin >> n >> D >> T;
    for (int i = 0; i < n; i++)
        cin >> t[i];
    stack<int> st;
    memset(par, -1, sizeof par);
    memset(lt, -1, sizeof lt);
    vector<int> tmp;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[st.top()] + i - st.top() > T) {
            tmp.pb(st.top());
            st.pop();
        }
        if (t[i] > T && st.empty())
            cnt++;
        if (!st.empty() && t[i] > T) {
            lt[i] = st.top();
            while (!tmp.empty() && tmp.back() >= lt[i]) {
                int j = tmp.back();
                if (lt[j] != -1) {
                    adj[i].pb(j);
                    par[j] = i;
                }
                tmp.pop_back();
            }
        }
        st.push(i);
    }
    for (int i = 0; i < n; i++) {
        if (par[i] == -1 && lt[i] != -1) {
            adj[n].pb(i);
            par[i] = n;
        }
    }
    dfs(n);
    tim--;
    build();
    vis[n] = true;
    int ans = 0;
    while (D--) {
        shift(1, 0, n);
        int v = seg[1];
        assert(mx[1] >= 0);
        if (mx[1] <= 0)
            break;
        ans += mx[1];
        while (!vis[v]) {
            upd(tin[v], tout[v]);
            vis[v] = true;
            v = par[v];
        }
    }
    assert(ans <= n);
    cout << n - ans - cnt << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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