Submission #879585

#	Time	Username	Problem	Language	Result	Execution time	Memory
879585		Shayan86	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	370 ms	336924 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll N = 2e6 + 50;
const ll inf = 1e9 + 7;

ll n, D, T, t[N], killer[N], res, m, h[N], far[N], par[N];

vector<int> adj[N], dead[N], root, height[N];

void dfs(int v){
    far[v] = v;
    for(int u: adj[v]){
        h[u] = h[v] + 1; par[u] = v; dfs(u);
        if(h[far[u]] > h[far[v]]) far[v] = far[u];
    }
}

int main(){
    fast_io;

    cin >> n >> D >> T;

    for(int i = 1; i <= n; i++){
        cin >> t[i];
        if(t[i] > T) t[i] = 0;
        else t[i] = min(n, i + T - t[i]);
    }

    vector<int> alive;
    for(int i = n; i > 0; i--){
        alive.pb(i);
        while(!alive.empty() && alive.back() <= t[i]){
            killer[alive.back()] = i; 
            dead[i].pb(alive.back());
            alive.pop_back();
        }
    }

    res = n - alive.size();

    vector<int> open;
    for(int i = 1; i <= n; i++){
        reverse(all(dead[i]));
        for(int v: dead[i]){
            if(v == i) continue;
            if(open.empty()) root.pb(++m);
            else adj[open.back()].pb(++m);
            open.pb(m);
        }
        if(!killer[i] || killer[i] == i) continue;
        open.pop_back();
    }

    for(int v: root){
        dfs(v); height[h[far[v]]].pb(far[v]);
    }

    int cur = m;
    while(cur >= 0 && D){
        if(height[cur].empty()){
            cur--; continue;
        }
        D--;
        int v = height[cur].back();
        height[cur].pop_back();
        while(par[v]){
            for(int u: adj[par[v]]){
                if(u == v) continue;
                height[h[far[u]] - h[u]].pb(far[u]); par[u] = 0;
            }
            v = par[v];
        }
        res -= cur+1;
    }

    cout << res;

}

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