제출 #1057364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057364		Piokemon	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	63 ms	155360 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];

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];
    }
    vector<pair<int,int>> stos;
    stos.push_back({2e9,-1});
    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;
    }
    int p=1;
    for (int x=1;x<=n;x++){
        if (a[x]<t)continue;
        while((a[p]<t || p<skad[x])&&p<x)p++;
        if (a[p]>=t && p<x){chron[x]=p;graf[p].push_back(x);}
    }
    for (int x=1;x<=n;x++){
        if (!odw[x]){
            par[x]=-1;
            dpt[x]=1;
            dfs(x);
        }
    }
    for (int x=base;x<=2*base;x++)tree[x]={-1e9,0};
    for (int x=1;x<=n;x++){
        if (a[x]>=t)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];
    }
    int odp=0;
    while(d--){
        int v=tree[1].second;
        while(v!=-1){
            odp++;
            add(1,1,base,pre[v],post[v],-1);
            v=par[v];
        }
    }
    cout << n-odp << '\n';
    return 0;
}

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