Submission #1360786

#TimeUsernameProblemLanguageResultExecution timeMemory
1360786NewtonabcThe short shank; Redemption (BOI21_prison)C++20
100 / 100
275 ms234544 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
ll a[N];
int re[N],p[N],pa[N],dp[N],nxt[N];
bool vs[N],fre[N];
vector<int> adj[N];
void dfs(int u,int p){
    dp[u]=1;
    vs[u]=1;
    nxt[u]=-1;
    for(auto v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        if(dp[v]+1>dp[u]){
            dp[u]=dp[v]+1;
            nxt[u]=v;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,d,t,ret=0; cin>>n >>d >>t;
    ret=n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int mx=INT_MIN;
    for(int i=1;i<=n;i++){
        if(a[i]<=t) mx=max(mx,(int)(i+t-a[i]));
        else{
            if(mx<i){
                fre[i]=1;
                ret--;
            }
        }
    }
    //cout<<ret <<"\n";
    stack<int> st;
    for(int i=n;i>=1;i--){
        if(fre[i]) continue;
        if(a[i]<=t) while(!st.empty() && i+t-a[i]>=st.top()) st.pop();
        if(a[i]>t){
            if(!st.empty()) adj[st.top()].push_back(i);
            st.push(i);
        }
    }
    priority_queue<pair<int,int>> q;
    for(int i=n;i>=1;i--){
        if(a[i]>t && !vs[i] && !fre[i]) dfs(i,i),q.push({dp[i],i});
    }
    while(!q.empty() && d!=0){
        d--;
        auto [del,u]=q.top();
        q.pop();
        ret-=del;
        while(true){
            for(auto v:adj[u]){
                if(v==nxt[u]) continue;
                q.push({dp[v],v});
            }
            u=nxt[u];
            if(u==-1) break;
        }
    }
    cout<<ret;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...