Submission #418068

#	Time	Username	Problem	Language	Result	Execution time	Memory
418068		balbit	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	577 ms	241672 KiB

prison

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT



const int maxn = 2e6+6;

int par[maxn];
bool done[maxn];
int to[maxn];
int h[maxn];
bool isleaf[maxn];
int dep[maxn];
vector<pii> hey;
vector<int>g[maxn];
void dfs(int v) {
    hey.pb({dep[v], v});
    for (int u : g[v]) {
        dep[u] = dep[v] + 1;
        dfs(u);
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(par, -1, sizeof par);
    memset(to, -1, sizeof to);
    int n,D,T;
    cin>>n>>D>>T;
    int mightreb = 0;
    int willreb = 0;
    vector<int> q;
    vector<int> tos;
    REP(i,n) {
        cin>>h[i];
        while (!q.empty() && h[q.back()] - q.back() > T - i ) {
            q.pop_back();
        }
        if (h[i] > T) {
            if (!q.empty() ) {
                to[i] = q.back();
                bug(i, to[i]);
//                isleaf[i] = 1;
                while (!tos.empty() && to[tos.back()] >= to[i]) {
//                    isleaf[i] = 0;
                    par[tos.back()] = i;
                    g[i].pb(tos.back());
                    tos.pop_back();
                }
                tos.pb(i);
                mightreb ++;
            }
        }else{
            willreb++;
        }
        q.pb(i);
    }

    REP(i,n) {
        if (to[i]!=-1 && par[i] == -1) {
            // is root
            dfs(i);
        }
    }
    sort(ALL(hey), greater<pii>());
    vector<int> tk;
    for (pii xx : hey) {
        int x = xx.s;
        if (done[x]) continue;
        int len = 0;
        for( int at = x; at != -1 && !done[at]; at = par[at]) {
            done[at] = 1;
            ++len;
        }
        tk.pb(len);
        bug(len);
    }
    sort(ALL(tk), greater<int>());
    REP(i, min(SZ(tk), D)) {
        mightreb -= tk[i];
    }
    bug(mightreb, willreb);
    cout<<mightreb + willreb<<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