Submission #1057438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057438		Piokemon	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	830 ms	415712 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 2e6;
int a[N+9];
int skad[N+9];
int chron[N+9];
vector<int> graf[N+9];
bool odw[N+9];
int tajm=1;
int pre[N+9];
int post[N+9];
int par[N+9];
int dpt[N+9];
int dang[N+9];
vector<int> prott[N+9];

void dfs(int v){
    if (odw[v])return;
    odw[v]=1;
    pre[v]=tajm++;
    for (int x:graf[v]){
        dpt[x]=dpt[v]+1;
        par[x]=v;
        dfs(x);
    }
    post[v]=tajm++;
}

constexpr int base=(1<<22);
pair<int,int> tree[2*base+9];
int lazy[2*base+9];

void daj(int x){
    tree[2*x].first+=lazy[x];tree[2*x+1].first+=lazy[x];
    lazy[2*x]+=lazy[x];lazy[2*x+1]+=lazy[x];
    lazy[x]=0;
}

void add(int x, int a, int b, int p, int k, int val){
    if (b<p || a>k)return;
    if (p<=a && b<=k){
        tree[x].first+=val;
        lazy[x]+=val;
        return;
    }
    daj(x);
    int mid=(a+b)/2;
    add(2*x,a,mid,p,k,val);
    add(2*x+1,mid+1,b,p,k,val);
    if (tree[2*x].first>=tree[2*x+1].first)tree[x]=tree[2*x];
    else tree[x]=tree[2*x+1];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,t;
    cin >> n >> d >> t;
    for (int x=1;x<=n;x++){
        cin >> a[x];
        if (a[x]>t)dang[x]=1;
    }
    vector<pair<int,int>> stos;
    stos.push_back({2e9,-1});
    int safe=0;
    for (int x=1;x<=n;x++){
        int rang=-1;
        if (a[x]<=t)rang=x+t-a[x];
        stos.push_back({rang,x});
        while(stos.back().first<x)stos.pop_back();
        skad[x]=stos.back().second;
        if (skad[x]==-1){
            dang[x]=0;
            safe++;
        }
        else{
            prott[skad[x]].push_back(x);
        }
    }
    priority_queue<int> chroni;chroni.push(-1e9);
    for (int x=1;x<=n;x++){
        for (int y:prott[x])chroni.push(-y);
        if (!dang[x])continue;
        while(-chroni.top()<=x)chroni.pop();
        if (-chroni.top()!=1e9)graf[-chroni.top()].push_back(x);
    }
    for (int x=n;x>=1;x--){
        if (!odw[x] && dang[x]){
            par[x]=-1;
            dpt[x]=1;
            dfs(x);
        }
    }
    for (int x=base;x<=2*base;x++)tree[x]={-1e9,-1};
    for (int x=1;x<=n;x++){
        if (dang[x])tree[base+pre[x]-1]={dpt[x],x};
    }
    for (int x=base-1;x>=1;x--){
        if (tree[2*x].first>=tree[2*x+1].first)tree[x]=tree[2*x];
        else tree[x]=tree[2*x+1];
    }
    for (int x=0;x<=n;x++)odw[x]=0;
    int odp=0;
    odw[0]=1;
    while(d--){
        int v=tree[1].second;
        while(v!=-1 && (!odw[v])){
            odp++;
            add(1,1,base,pre[v],post[v],-1);odw[v]=1;
            v=par[v];
        }
    }
    cout << n-safe-odp << '\n';
    return 0;
}

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