Submission #973801

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

prison

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

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,d,t;
    cin >> n >> d >> t;
    vi times(n);
    int last_reb=-1;
    vector<pi> q;
    vi inact(n,-1);
    vi next;
    int rebc=0;
    for (int i=0; i<n; i++) {
        cin >> times[i];
        last_reb=max(last_reb,i+t-times[i]);
        if (q.size()) {
            q.back().se=max(q.back().se,i+t-times[i]);
        }
        if (times[i]>t && last_reb>=i) {
            rebc++;
            int loc_last_reb=-1;
            while (q.size()) {
                auto [ind,new_reb]=q.back();
                loc_last_reb=max(loc_last_reb,new_reb);
                if (loc_last_reb>=i) {
                    break;
                }
                next[inact[ind]]=next.size();
                q.pop_back();
            }
            q.pb({i,-1});
            inact[i]=next.size();
            next.pb(-1);
        }
        else if (times[i]<=t) {
            rebc++;
        }
    }
    vector<vi> graph(next.size());
    vi maxdepth(next.size(),1);
    vi maxchild(next.size(),-1);
    vector<bool> ok(next.size(),1);
    for (int i=0; i<next.size(); i++) {
        if (next[i]!=-1) {
            graph[next[i]].pb(i);
            ok[i]=0;
            if (maxdepth[i]+1>maxdepth[next[i]]) {
                maxdepth[next[i]]=maxdepth[i]+1;
                maxchild[next[i]]=i;
            }
        }
    }
    priority_queue<pi> qu;
    for (int i=0; i<next.size(); i++) {
        if (ok[i]) {
            qu.emplace(maxdepth[i],i);
        }
    }
    for (int i=0; i<d; i++) {
        if (!qu.size()) {
            break;
        }
        auto [depth,j]=qu.top();
        qu.pop();
        rebc-=depth;
        while (j!=-1 && graph[j].size()) {
            for (auto to:graph[j]) {
                if (to!=maxchild[j]) {
                    qu.emplace(maxdepth[to],to);
                }
            }
            j=maxchild[j];
        }
    }
    cout << rebc << '\n';
    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i=0; i<next.size(); i++) {
      |                   ~^~~~~~~~~~~~
prison.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i=0; i<next.size(); i++) {
      |                   ~^~~~~~~~~~~~

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