oj.uz

Submission #940513

# Submission time Handle Problem Language Result Execution time Memory
940513 2024-03-07T10:09:29 Z LucaIlie The short shank; Redemption (BOI21_prison) C++17
0 / 100
 5 ms 8796 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 7.5e4;
const long long INF = 1e9;
const long double eps = 1e-3;

int groups[MAX_N + 1], firstLower[MAX_N + 1];
long long t[MAX_N + 1];
long long minPrisoners[MAX_N + 1];

struct info {
    long long minn;
    int pos;

    bool operator < ( const info &x ) const {
        return minn < x.minn;
    }
};

struct SegTree {
    int n, ls, rs;
    info segTree[4 * MAX_N];
    long long lazy[4 * MAX_N];

    void init( int v, int l, int r ) {
        lazy[v] = 0;
        if ( l == r ) {
            segTree[v] = { 0, l };
            return;
        }
        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
        segTree[v] = min( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    void init( int _ls, int _rs ) {
        ls = _ls;
        rs = _rs;
        n = rs - ls + 1;
        init( 0, ls, rs );
    }

    void propag( int v, int l, int r ) {
        segTree[v].minn += 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, long long 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, long long x ) {
        update( 0, ls, rs, l, r, x );
    }

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

        if ( l > rq || r < lq )
            return { INF, 0 };

        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() {
    ifstream cin( ".in" );
    /*cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );*/
    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];
    }


    cout << fixed << setprecision( 15 );
    int lc = 0, rc = 1e6;
    while ( rc - lc > 1 ) {
        int cost = (rc + lc) / 2;

        //cout << lc << " " << rc << "\n";
        prisoners.init( 1, n );
        for ( int i = 1; i <= n; i++ ) {
            prisoners.update( i, i, minPrisoners[i - 1] + cost );
            prisoners.update( 1, firstLower[i], 1 );

            auto x = prisoners.query( 0, 1, n, 1, i );
            minPrisoners[i] = x.minn;
            groups[i] = groups[x.pos - 1] + 1;
        }

        if ( groups[n] > d )
            lc = cost;
        else
            rc = cost;
    }
    int cost = rc;
    prisoners.init( 1, n );
    for ( int i = 1; i <= n; i++ ) {
        prisoners.update( i, i, minPrisoners[i - 1] + cost );
        prisoners.update( 1, firstLower[i], 1 );

        auto x = prisoners.query( 0, 1, n, 1, i );
        minPrisoners[i] = x.minn;
        groups[i] = groups[x.pos] + 1;
    }

    cout << minPrisoners[n] - d * cost;

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 8796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -