Submission #934193

#	Time	Username	Problem	Language	Result	Execution time	Memory
934193		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1627 ms	366524 KiB

prison

#include "bits/stdc++.h"

using namespace std;
#define int long long

#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
pair<int,int> seg[8000001];
int lazy[8000001];
vector<int> adj[2000001];
bool vis[2000001];
int p[2000001],in[2000001],out[2000001];
void prop(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val,int nah){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        if(nah!=-1&&l==r){
            seg[p].second = nah;
        }
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val,nah);
    update(p*2+1,md+1,r,lq,rq,val,nah);
    seg[p] = max(seg[p*2],seg[p*2+1]);
}
int get(int p,int l,int r,int idx){
    prop(p,l,r);
    if(l==r)return seg[p].first;
    int md = (l+r)/2;
    if(idx<=md)return get(p*2,l,md,idx);
    else return get(p*2+1,md+1,r,idx);
}
int timer = 0;
void dfs(int i,int pr,int dep){
    p[i] = pr;
    in[i] = ++timer;
    update(1,1,n,in[i],in[i],dep,i);
    for(auto j:adj[i]){
        dfs(j,i,dep+1);
    }
    out[i] = timer;
}
void ers(int idx){
    vis[idx] = 1;
    int nah = get(1,1,n,in[idx]);
    for(auto j:adj[idx]){
        if(vis[j])continue;
        update(1,1,n,in[j],out[j],-nah-1,-1);
    }
    update(1,1,n,in[idx],in[idx],-1e9,-1);
    if(p[idx]!=-1&&vis[p[idx]]==0)ers(p[idx]);
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int d,T;
    cin>>n>>d>>T;
    n++;
    int arr[n];
    for(int i = 1;i<n;i++)cin>>arr[i];
    arr[0] = 1e10;
    stack<pair<int,int>> s;
    int nxt[n];
    for(int i = n-1;i>=0;i--){
        while(!s.empty()&&arr[s.top().first]-s.top().first>=arr[i]-i)s.pop();
        int nah = max(0ll,T+1-arr[i])+i;
        if(nah==i){
            int lol = 0;
            if(!s.empty()&&s.top().first==i+1){
                lol = s.top().second;
            }else{
                lol = i+1;
            }
            nxt[i] = lol;
            s.push({i,nah});
        }else{
            int a3 = nah;
            if(!s.empty()&&s.top().first<=nah){
                a3 = s.top().second;
            }
            nxt[i] = a3;
            s.push({i,a3});
        }
        if(arr[i]<=T)nxt[i] = -1;
        if(nxt[i]>=n)nxt[i] = -1;
    }
    for(int i = 0;i<n;i++){
        if(nxt[i]!=-1){
            adj[nxt[i]].push_back(i);
        }
    }
    for(int i = n-1;i>=0;i--){
        if(in[i]==0){
            dfs(i,-1,0);
        }
    }
    int fin = 0;
    for(int i = 0;i<n;i++){
        if(arr[i]<=T){
            fin++;
            vis[i] = 1;
            update(1,1,n,in[i],in[i],-1e9,-1);
        }
    }
    int de = 0;
    if(vis[de]==0)ers(de);
    for(int i = 1;i<=d;i++){
        int de = seg[1].second;
        if(vis[de])continue;
        ers(de);
    }
    for(int i = 0;i<n;i++){
        if(!vis[i])fin++;
    }
    cout<<fin<<endl;
}

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