Submission #672807

#	Time	Username	Problem	Language	Result	Execution time	Memory
672807		radal	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2053 ms	303332 KiB

prison

// In the name of God
#pragma GCC optimize("Ofast", "unroll-loops")
 
#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 = 2e6 + 5, M = 4194310;
int n, D, T;
int t[N], L[N];
bool vis[N];
vector<int> vec[M];
int seg[M], mx[M], lz[M];
 
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 val, int v = 1, int tl = 0, int tr = n - 1) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        lz[v] += val;
        shift(v, tl, tr);
        return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, val, v << 1, tl, mid);
    upd(l, r, val, v << 1 | 1, mid + 1, tr);
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    if (mx[v] == mx[v << 1])
        seg[v] = seg[v << 1];
    else
        seg[v] = seg[v << 1 | 1];
}
void add(int i, int r, int v = 1, int tl = 0, int tr = n - 1) {
    if (tl == tr && tl == i) {
        vec[v].pb(r);
        return;
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid)
        add(i, r, v << 1, tl, mid);
    else
        add(i, r, v << 1 | 1, mid + 1, tr);
}
void buildSeg(int v = 1, int tl = 0, int tr = n - 1) {
    seg[v] = tl;
    if (tl == tr)
        return;
    int mid = (tl + tr) >> 1;
    buildSeg(v << 1, tl, mid);
    buildSeg(v << 1 | 1, mid + 1, tr);
}
 
void build(int v = 1, int tl = 0, int tr = n - 1) {
    if (tl == tr) {
        sort(vec[v].begin(), vec[v].end());
        vec[v].shrink_to_fit();
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1 | 1, mid + 1, tr);
    int l = 0, r = 0;
    int lc = v << 1, rc = v << 1 | 1;
    while (l < (int)vec[lc].size() && vec[lc][l] < tr)
        l++;
    while (r < (int)vec[rc].size() && vec[rc][r] < tr)
        r++;
    while (l < (int)vec[lc].size() && r < (int)vec[rc].size()) {
        if (vec[lc][l] <= vec[rc][r]) {
            vec[v].pb(vec[lc][l++]);
            l++;
        }
        else
            vec[v].pb(vec[rc][r++]);
    }
    while (l < (int)vec[lc].size())
        vec[v].pb(vec[lc][l++]);
    while (r < (int)vec[rc].size())
        vec[v].pb(vec[rc][r++]);
    //vec[v].shrink_to_fit();
}
void rem(int r, int v = 1, int tl = 0, int tr = n - 1) {
    if (tr <= r) {
        while (!vec[v].empty() && vec[v].back() >= r) {
            int u = vec[v].back();
            vec[v].pop_back();
            if (!vis[u]) {
                upd(L[u], u, -1);
                vis[u] = true;
            }
        }
        vec[v].shrink_to_fit();
        return;
    }
    int mid = (tl + tr) >> 1;
    rem(r, v << 1, tl, mid);
    if (r > mid)
        rem(r, v << 1 | 1, mid + 1, tr);
}
 
 
void solve() {
    cin >> n >> D >> T;
    for (int i = 0; i < n; i++)
        cin >> t[i];
 
    vector<int> st;
    int ans = 0;
    buildSeg();
    for (int i = 0; i < n; i++) {
        while (!st.empty() && (t[st.back()] >= t[i] || t[st.back()] + i - st.back() > T))
            st.pop_back();
        if (!st.empty() && t[i] > T) {
            // st.top(), i - 1
            L[i - 1] = st.back();
            add(st.back(), i - 1);
            upd(st.back(), i - 1, 1);
        }
        else
            ans += t[i] > T;
        st.pb(i);
    }
    build();
    while (D--) {
        shift(1, 0, n - 1);
        int i = seg[1];
        ans += mx[1];
        rem(i);
    }
    cout << n - ans << '\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