Submission #1288937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288937		djawadmain	The short shank; Redemption (BOI21_prison)	C++20	10 / 100	252 ms	83264 KiB

prison

#include<iostream>
#include<vector>

using namespace std;

#define ll long long
#define ld long double
#define pii pair<int, int>
#define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0));
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define maxn 2000000

int seg[maxn << 2], lazy[maxn << 2];
int cn[maxn];

vector<int> segr[maxn << 2];

pii ra[maxn];

bool it[maxn];

int n;

void build(int l, int r, int id){

    if (l == r){

        seg[id] = cn[l];
        lazy[id] = cn[l];

        return;
    }

    int mid = (l + r) >> 1;

    build(l, mid, id << 1);
    build(mid + 1, r, (id << 1) + 1);

    seg[id] = max(seg[id << 1], seg[(id << 1) + 1]);
}

void upd(int l, int r, int s, int e, int id){

    if (s > r or e < l) return;
    if (s <= l and e >= r){

        lazy[id]--;
        seg[id]--;

        return;
    }

    int mid = (l + r) >> 1;

    upd(l, mid, s, e, id << 1);
    upd(mid + 1, r, s, e, (id << 1) + 1);

    seg[id] = max(seg[id << 1], seg[(id << 1) + 1]) + lazy[id];
}

void add_range(int l, int r, int ind, int id){

    segr[id].pb(ind);

    if (l == r) return;

    int mid = (l + r) >> 1;
    int s = ra[ind].ff;

    if (s <= mid) add_range(l, mid, ind, id << 1);
    else add_range(mid + 1, r, ind, (id << 1) + 1);
}

void remove_range(int l, int r, int rp, int id){

    if (rp >= r){

        while (not segr[id].empty() and ra[segr[id].back()].ss >= rp){

            int np = segr[id].back();
            int s = ra[np].ff, e = ra[np].ss;

            if (not it[np]){

                it[np] = true;
                upd(0, n - 2, s, e, 1);
            }

            segr[id].pop_back();
        }

        return;
    }

    int mid = (l + r) >> 1;

    remove_range(l, mid, rp, id << 1);
    if (rp > mid) remove_range(mid + 1, r, rp, (id << 1) + 1);

}

int FM(int l, int r, int id){

    if (l == r) return l;

    int mid = (l + r) >> 1;

    if (seg[id << 1] >= seg[(id << 1) + 1]) return FM(l, mid, id << 1);
    
    return FM(mid + 1, r, (id << 1) + 1);
}

int D, T;

int tm[maxn], CI[maxn], CO[maxn];

int main(){

    RUN_LIKE_DJAWAD

    cin >> n >> D >> T;

    for (int i = 0; i < n; i++) cin >> tm[i];

    if (n == 1){

        if (tm[0] <= T) cout << 1 << "\n";
        else cout << 0 << "\n";

        return 0;
    }

    int ans = n;

    vector<int> stk;

    int c = 0;

    for (int i = 0; i < n; i++){

        while (not stk.empty() and tm[stk.back()] + (i - stk.back()) > T) stk.pop_back();

        if (tm[i] > T){
            
            if (not stk.empty()) ra[c++] = {stk.back(), i - 1};
            else ans--;

        } else stk.pb(i);
    }

    for (int i = c - 1; i >= 0; i--) add_range(0, n - 2, i, 1);

    for (int i = 0; i < c; i++){

        CI[ra[i].ff]++;
        CO[ra[i].ss]--;
    }

    int cnn = 0;

    for (int i = 0; i < n - 1; i++){

        cnn += CI[i];
        cn[i] = cnn;
        cnn += CO[i];
    }

    build(0, n - 2, 1);

    while (D--){

        ans -= seg[1];

        int nrp = FM(0, n - 2, 1);

        remove_range(0, n - 2, nrp, 1);
    }

    cout << ans << "\n";
}

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