Submission #948023

#	Time	Username	Problem	Language	Result	Execution time	Memory
948023		LucaIlie	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	2058 ms	110420 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e6;
const long long INF = 1e9;

bool vis[MAX_N + 1];
int parent[MAX_N + 1], firstLower[MAX_N + 1], depth[MAX_N + 1], pos[MAX_N + 1];
long long t[MAX_N + 1];
vector<int> adj[MAX_N + 1], opt[MAX_N + 1];

int comp;
void dfs( int u ) {
    vis[u] = true;
    for ( int v: adj[u] ) {
        depth[v] = depth[u] + 1;
        dfs( v );
    }
    if ( adj[u].size() == 0 )
        opt[comp].push_back( depth[u] );
}

int main() {
    //ifstream cin( ".in" );
    cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );
    int n, d, s;

    cin >> n >> d >> s;
    for ( int i = 1; i <= n; i++ )
        cin >> t[i];
    t[0] = -INF;

    vector<int> stack;
    stack.push_back( 0 );
    firstLower[0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        while ( t[i] - i <= t[stack.back()] - stack.back() )
            stack.pop_back();
        stack.push_back( i );

        int l = 0, r = stack.size();
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;

            if ( t[stack[mid]] + i - stack[mid] <= s )
                l = mid;
            else
                r = mid;
        }
        firstLower[i] = stack[l];
    }

    for ( int i = 1; i <= n; i++ ) {
        if ( t[i] <= s )
            continue;

        parent[i] = i + 1;
        while ( parent[i] <= n && !(t[parent[i]] > s && firstLower[parent[i]] < i) )
            parent[i]++;
        //cout << i << " " << parent[i] << "\n";
        adj[parent[i]].push_back( i );
    }

    priority_queue<pair<int, int>> pq;
    for ( int i = n; i >= 1; i-- ) {
        if ( t[i] <= s )
            continue;

        depth[i] = 1;
        dfs( i );
        sort( opt[comp].begin(), opt[comp].end() );
        reverse( opt[comp].begin(), opt[comp].end() );
        pq.push( { opt[comp][0], comp } );
        comp++;
    }

    int ans = n;
    while ( d > 0 && !pq.empty() ) {
        auto x = pq.top();
        pq.pop();
        int c = x.second;
        ans -= x.first;

        pos[c]++;
        //cout << x.first << "\n";
        if ( pos[c] < opt[c].size() )
            pq.push( { opt[c][pos[c]] - pos[c], c } );

        d--;
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if ( pos[c] < opt[c].size() )
      |              ~~~~~~~^~~~~~~~~~~~~~~

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