Submission #948710

#	Time	Username	Problem	Language	Result	Execution time	Memory
948710		LucaIlie	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	532 ms	255904 KiB

prison

#include <bits/stdc++.h>

using namespace std;

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

struct aa {
    int val, node;

    bool operator < ( const aa &a ) const {
        return val < a.val;
    }

    aa operator - ( int a ) {
        return { val - a, node };
    }
};

bool vis[MAX_N + 1], isPassive[MAX_N + 1];
int parent[MAX_N + 1], firstLower[MAX_N + 2], depth[MAX_N + 1];
aa maxDepth[MAX_N + 1];
long long t[MAX_N + 2];
vector<int> adj[MAX_N + 2];

void dfs( int u ) {
    vis[u] = true;
    maxDepth[u] = { depth[u], u };
    for ( int v: adj[u] ) {
        depth[v] = depth[u] + 1;
        dfs( v );
        maxDepth[u] = max( maxDepth[u], maxDepth[v] );
    }
}

int main() {
    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];

        if ( firstLower[i] == 0 )
            isPassive[i] = vis[i] = true;
    }

    stack.clear();
    stack.push_back( n + 1 );
    firstLower[n + 1] = -1;
    for ( int i = n; i >= 1; i-- ) {
        if ( t[i] <= s || isPassive[i] )
            continue;

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

            if ( firstLower[stack[mid]] < i )
                l = mid;
            else
                r = mid;
        }
        parent[i] = stack[l];
        adj[parent[i]].push_back( i );

        while ( firstLower[i] <= firstLower[stack.back()] )
            stack.pop_back();
        stack.push_back( i );
    }

    priority_queue <aa> pq;
    for ( int v = n; v >= 1; v-- ) {
        if ( t[v] <= s || vis[v] )
            continue;

        depth[v] = 1;
        dfs( v );
        pq.push( maxDepth[v] );
    }
    for ( int v = n; v >= 1; v-- )
        vis[v] = false;

    while ( d > 0 && !pq.empty() ) {
        auto x = pq.top();
        pq.pop();

        int u = x.node;
        while ( u != n + 1 ) {
            isPassive[u] = true;
            for ( int v: adj[u] ) {
                parent[v] = n + 1;
                if ( isPassive[v] )
                    continue;
                pq.push( maxDepth[v] - depth[u] );
            }
            u = parent[u];
        }

        d--;
    }

    int ans = n;
    for ( int v = 1; v <= n; v++ )
        ans -= isPassive[v];
    cout << ans;

    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