Submission #1190871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190871		DanielPr8	The short shank; Redemption (BOI21_prison)	C++20	55 / 100	2093 ms	143300 KiB

prison

#include <bits/stdc++.h>

using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

ll cur=2;
ll lc[ll(3e7)]={0}, rc[ll(3e7)]={0}, v[ll(3e7)]={0};
void sparse(ll i, ll l, ll r){
    if(l+1<r){
        if(!lc[i])lc[i]=cur++;
        if(!rc[i])rc[i]=cur++;
    }
}
void seg(ll a, ll b){
    lc[cur]=a;
    rc[cur]=b;
    v[cur++]=v[a]+v[b];
}
void seg(ll x){
    v[cur++]=x;
}
ll que(ll i, ll l, ll r, ll a, ll b){
    if(r<=a || b<=l)return 0;
    if(a<=l && r<=b)return v[i];
    if(v[i]==0)return 0;
    sparse(i, l, r);
    return que(lc[i], l, (l+r)/2, a, b)+que(rc[i], (l+r)/2, r, a, b);
}
ll upd(ll i, ll l, ll r, ll t, ll x){
    sparse(i, l, r);
    if(l+1==r){
        seg(v[i]+x);
        return cur-1;
    }
    if(t>=(l+r)/2){
        seg(lc[i], upd(rc[i], (l+r)/2, r, t, x));
        return cur-1;
    }
    else{
        seg(upd(lc[i], l, (l+r)/2, t, x), rc[i]);
        return cur-1;
    }
}
vll hea;
ll N, m;
vvl dp;
void calc(ll a, ll b, ll j, ll mn, ll mx){
    if(a>=b)return;
    ll i = (a+b)/2;
    ll bes = mn;
    for(ll h = mn; h < mx && h<i; ++h){
        ll p = dp[0][h] + que(hea[i], 0, N, h, i);
        if(p>dp[1][i]){
            bes=h;
            dp[1][i]=p;
        }
    }
    if(a+1<b){
        calc(a, (a+b)/2, j, mn, bes+1);
        calc((a+b)/2+1, b, j, bes, mx);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, a, b, d, t;
    cin >> n >> d >> t;
    N = 1<<(32-__builtin_clz(n-1));
    vll tm(n), ls(n);
    stack<pll> w;
    w.push({-1e9, -1});
    for(ll i = 0; i < n; ++i){
        cin >> tm[i];
        w.push({tm[i], i});
        while(w.top().f+i-w.top().s>t){
            w.pop();
        }
        ls[i]=w.top().s;
    }
    ll ans = n, m=n;
    hea = vll(N+1,1);
    for(ll i = n-1; i >= 0; --i){
        hea[i]=hea[i+1];
        if(ls[i]!=-1)hea[i] = upd(hea[i], 0, N, ls[i], 1);
        else m--;
    }
    dp = vvl(2, vll(n));
    for(ll j = 1; j <= d; ++j){
        calc(0, n, j, 0, n);
        swap(dp[0], dp[1]);
        dp[1]=vll(n,0);
    }
    for(ll i = 0; i < n; ++i){
        ans = min(ans, m-dp[0][i]);
    }
    cout << ans;
}

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