제출 #939661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939661		LucaIlie	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	2063 ms	62144 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e6;
const int MAX_D = 16;
const int INF = MAX_N + 1;

int minPrisoners[MAX_N + 1][MAX_D + 1], t[MAX_N + 1], firstLower[MAX_N + 1];

struct SegTree {
    int n, ls, rs;
    vector<int> segTree, lazy;

    void init( int _n, int _ls, int _rs ) {
        n = _n;
        ls = _ls;
        rs = _rs;
        segTree.resize( 4 * n );
        lazy.resize( 4 * n );
        for ( int v = 0; v < 4 * n; v++ )
            segTree[v] = lazy[v] = 0;
    }

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru, int x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] += x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = min( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    void update( int l, int r, int x ) {
        update( 0, ls, rs, l, r, x );
    }

    int query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return INF;

        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        return min( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
    }
} prisoners;

int main() {
    int n, d, s;

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

    vector<int> stack;
    stack.push_back( 0 );
    for ( int i = 1; i <= n; i++ ) {
        while ( t[i] <= t[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]] <= s - i )
                l = mid;
            else
                r = mid;
        }
        firstLower[i] = stack[l];
    }

    minPrisoners[0][0] = 0;
    for ( int i = 1; i <= n; i++ )
        minPrisoners[i][0] = INF;
    for ( int k = 1; k <= d; k++ ) {
        minPrisoners[0][k] = INF;
        prisoners.init( n, 1, n );
        for ( int i = 1; i <= n; i++ ) {
            prisoners.update( i, i, minPrisoners[i - 1][k - 1] );
            prisoners.update( 1, firstLower[i], 1 );

            minPrisoners[i][k] = prisoners.query( 0, 1, n, 1, i );
        }
    }

    cout << minPrisoners[n][d] << "\n";

    return 0;
}

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