Submission #398476

#	Time	Username	Problem	Language	Result	Execution time	Memory
398476		model_code	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	632 ms	213652 KiB

prison

#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

int main()
{
    int N, D, T; scanf("%d %d %d", &N, &D, &T);

    int last_rebel = -1;
    int num_rebels = 0;
    vector<int> inactive(N, -1);
    vector<int> times(N);
    vector<int> next;
    stack<pii> S;

    for(int i = 0; i < N; ++i)
    {
        int t; scanf("%d", &t);
        times[i] = t;

        last_rebel = max(last_rebel, i + T - t);

        if(not S.empty()) S.top().second = max(S.top().second, i + T - t);

        if(t > T and last_rebel >= i)
        {
            int last_rebel_internal = -1;
            ++num_rebels;

            while(not S.empty())
            {
                pii curr = S.top();
                int j = curr.first;

                last_rebel_internal = max(last_rebel_internal, curr.second);
                if(last_rebel_internal >= i) break;

                next[inactive[j]] = next.size();
                S.pop();
            }

            S.emplace(i, -1);

            inactive[i] = next.size();
            next.push_back(-1);
        }

        if(t <= T) ++num_rebels;
    }

    vector<vector<int>> children(next.size());
    vector<int> subtree_height(next.size(), 1);
    vector<int> max_subtree(next.size(), -1);
    vector<vector<int>> PQpre(next.size() + 1);
    deque<pii> PQ;
    vector<char> erased(next.size(), false);

    for(int i = 0; i < next.size(); ++i)
    {
        int j = next[i];

        if(j != -1)
        {
            children[j].push_back(i);

            int new_height = subtree_height[i] + 1;

            if(new_height > subtree_height[j])
            {
                subtree_height[j] = new_height;
                max_subtree[j] = children[j].size() - 1;
            }
        }

        PQpre[subtree_height[i]].push_back(i);
    }

    for(int i = PQpre.size() - 1; i >= 0; --i)
        for(int x : PQpre[i]) PQ.emplace_back(i, x);

    int stopped = 0;

    for(int i = 0; i < D and not PQ.empty(); ++i)
    {
        pii curr = PQ.front(); PQ.pop_front();
        stopped += curr.first;

        int j;
        for(j = curr.second; max_subtree[j] != -1 and not erased[j]; j = children[j][max_subtree[j]])
            erased[j] = true;
        erased[j] = true;

        while(not PQ.empty() and erased[PQ.front().second]) PQ.pop_front();
    }
    
    printf("%d\n", num_rebels - stopped);
    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < next.size(); ++i)
      |                    ~~^~~~~~~~~~~~~
prison.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     int N, D, T; scanf("%d %d %d", &N, &D, &T);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |         int t; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~

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