Submission #1190848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190848		DanielPr8	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	227 ms	135996 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;
ll query(ll a, ll b, ll c, ll d){//in range (a,b) que(c,d)
    return que(hea[a], 0, N, c, d) - que(hea[b], 0, N, c, d);
}
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[h][j-1] + query(i, n-1, h, i);
        if(p>dp[i][j]){
            bes=h;
            dp[i][j]=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 cur--;
    }
    
    for(ll i = 0; i < n; ++i){
        ans = min(ans, m-query(i, N, 0, i));
    }
    /*dp = vvl(n, vll(d+1));
    for(ll j = 1; j <= d; ++j){
        calc(0, n, j, 0, n);
    }
    ll ans = n;
    for(ll i = 0; i < n; ++i){
        ans = min(ans, n-dp[i][d]);
    }*/
    cout << ans;
}

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