Submission #1184608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184608		kl0989e	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	504 ms	234196 KiB

prison

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

#pragma GCC optimize("Ofast")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e6+10;

vector<vi> graph(maxn);
vi sze(maxn,-1);
vi mxnode(maxn,0);
vi prv(maxn,-1);

void dfs(int cur) {
    sze[cur]=1;
    if (graph[cur].size()==0) {
        mxnode[cur]=cur;
        return;
    }
    mxnode[cur]=graph[cur][0];
    for (auto to:graph[cur]) {
        dfs(to);
        if (sze[to]+1>sze[cur]) {
            sze[cur]=sze[to]+1;
            mxnode[cur]=mxnode[to];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,d,t;
    cin >> n >> d >> t;
    vi a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    vi stk;
    vector<pi> stk2;
    int mx=-1;
    int sub=0;
    for (int i=0; i<n; i++) {
        if (a[i]>t) {
            if (mx>=i) {
                while (stk2.back().fi<i) {
                    stk2.pop_back();
                }
                while (stk.size() && stk.back()>stk2.back().se) {
                    prv[stk.back()]=i;
                    graph[i].pb(stk.back());
                    stk.pop_back();
                }
                stk.pb(i);
            }
            else {
                sub++;
            }
        }
        else {
            mx=max(mx,i+t-a[i]);
            stk2.push_back({i+t-a[i],i});
        }
    }
    priority_queue<pi> q;
    while (stk.size()) {
        int a=stk.back();
        stk.pop_back();
        dfs(a);
        q.push({sze[a],mxnode[a]});
    }
    while (d-- && q.size()) {
        auto [s,a]=q.top();
        q.pop();
        sub+=s;
        while (prv[a]!=-1) {
            int na=prv[a];
            for (auto to:graph[na]) {
                if (to!=a) {
                    q.push({sze[to],mxnode[to]});
                    prv[to]=-1;
                }
            }
            a=prv[a];
        }
    }
    cout << n-sub << '\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