Submission #481894

#	Time	Username	Problem	Language	Result	Execution time	Memory
481894		radal	The short shank; Redemption (BOI21_prison)	C++14	55 / 100	698 ms	36908 KiB

prison

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N = 5e5+20,mod = 1e9+7,inf = 2e9,sq = 400;
int poww(int n,ll k){
    if (!k) return 1;
    if (k == 1) return n;
    int r = poww(n,k/2);
    return 1ll*r*r%mod*poww(n,k&1)%mod;
}
inline int mkay(int x,int y){
    if (x+y < mod) return x+y;
    return x+y-mod;
}
int dp[N][2],seg[4*N][2],lz[4*N][2];
int t[N],l[N],a[N],cnt[N];
bool mark[N];
void build(int l,int r,int p,int x,int v,bool f){
    if (r-l == 1){
        seg[v][f] = x;
        lz[v][f] = 0;
        return;
    }
    lz[v][f] = 0;
    int m = (l+r) >> 1,u = (v << 1);
    if (p < m) build(l,m,p,x,u,f);
    else build(m,r,p,x,u|1,f);
    seg[v][f] = min(seg[u][f],seg[u|1][f]);
}
void upd(int l,int r,int s,int e,int v,bool f){
    if (e <= s || l >= e || s >= r) return;
    if (l >= s && e >= r){
        seg[v][f]++;
        lz[v][f]++;
        return;
    }
    int m = (l+r) >> 1, u = (v << 1);
    if (lz[v][f]){
        lz[u][f] += lz[v][f];
        lz[u|1][f] += lz[v][f];
        seg[u][f] += lz[v][f];
        seg[u|1][f] += lz[v][f];
        lz[v][f] = 0;
    }
    upd(l,m,s,e,u,f);
    upd(m,r,s,e,u|1,f);
    seg[v][f] = min(seg[u][f],seg[u|1][f]);
}
int que(int l,int r,int s,int e,int v,bool f){
    if (l >= s && e >= r) return seg[v][f];
    if (s >= r || l >= e) return inf;
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v][f]){
        lz[u][f] += lz[v][f];
        lz[u|1][f] += lz[v][f];
        seg[u][f] += lz[v][f];
        seg[u|1][f] += lz[v][f];
        lz[v][f] = 0;
    }
    return min(que(l,m,s,e,u,f),que(m,r,s,e,u|1,f));
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,d,T;
    cin >> n >> d >> T;
    d = min(d,n-1);
    stack<int> st;
    rep(i,0,n){
        cin >> t[i];
        if (i) dp[i][0] = dp[i-1][0];
        else dp[i][0] = 0;
        if (t[i] <= T){
            l[i] = i;
            dp[i][0]++;
            build(0,n,i,dp[i][0],1,0);
            st.push(i);
            continue;
        }
        while (!st.empty() && i-st.top()+t[st.top()] > T) st.pop();
        if (st.empty()){
            l[i] = -1;
            build(0,n,i,dp[i][0],1,0);
            continue;
        }
        dp[i][0]++;
        build(0,n,i,dp[i][0],1,0);
        l[i] = st.top();
        cnt[l[i]]++;
    }
    vector<pll> ve;
    rep(i,0,n) ve.pb({cnt[i],i});
    sort(ve.begin(),ve.end());
    repr(i,n-1,n-d){
        mark[ve[i].Y] = 1;
    }
    int ans = 0,ans2 = 0;
    int x = inf;
    rep(i,0,n){
        if (t[i] <= T || x+1 <= T){
            ans++;
            if (mark[i]) x= inf;
            else x = min(x+1,t[i]);
            continue;
        }
    }
    if (1ll*n*d*10 > 3*100000000){
        rep(j,0,300){
            mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
            shuffle(ve.begin(),ve.end(),rng);
            int f = 0;
            rep(i,0,n){
                mark[ve[i].Y] = 0;
                if (f < d && ve[i].X && t[ve[i].Y+1] > T ){
                    f++;
                    mark[ve[i].Y] = 1;
                }
            }
            x = inf;
            ans2 = 0;
            rep(i,0,n){
                if (t[i] <= T || x+1 <= T){
                    ans2++;
                    if (ans2 >= ans) break;
                    if (mark[i]) x= inf;
                    else x = min(x+1,t[i]);
                    continue;
                }
            }
            ans = min(ans,ans2);
        }
        cout << ans;
        return 0;
    }
    rep(i,1,d+1){
        bool x = (i&1);
        dp[0][x] = dp[0][1-x];
        build(0,n,0,dp[0][x],1,x);
        rep(j,1,n){
            upd(0,n,0,l[j],1,1-x);
            dp[j][x] = que(0,n,0,j,1,1-x);
            build(0,n,j,dp[j][x],1,x);
        }
    }
    cout << dp[n-1][d&1];
}

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