Submission #442019

#	Time	Username	Problem	Language	Result	Execution time	Memory
442019		Ozy	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	2071 ms	19500 KiB

prison

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 500000

lli n,t,d,act,a,res,op;
lli arr[MAX+2],grupo[MAX+2],bit[MAX+2];
stack<lli> pila;

void actualiza(lli pos) {
    while (pos <= n) {
        bit[pos]++;
        pos += pos&(-pos);
    }
}

lli query(lli pos) {
    lli total = 0;
    while (pos > 0) {
        total += bit[pos];
        pos -= pos & (-pos);
    }
    return total;
}

lli busca() {
    lli sum,mayor=0;
    lli pos = -1;

    sum = 0;
    repa(i,n,1) {
        if (grupo[i] == 0) continue;
        if (grupo[i] == i) {
            sum = query(i);
            if (sum > mayor) {
                mayor = sum;
                pos = i;
            }
        }
        actualiza(grupo[i]);
    }

    return pos;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> d >> t;
    rep(i,1,n) cin >> arr[i];
    res = n;

    rep(i,1,n) {
        if (arr[i] <= t) {
            pila.push(i);
            grupo[i] = i;
        }
        else {
            while (!pila.empty()) {
                act = pila.top();

                a = arr[act] + (i-act);
                if (a <= t) {grupo[i] = act;break;}
                else pila.pop();
            }
            if (grupo[i] == 0) res--;
        }

    }

    rep(q,1,d) {

        rep(i,1,n) bit[i] = 0;
        op = busca();
        if (op == -1) break;

        rep(i,op+1,n) {
            if (grupo[i] <= op && grupo[i] > 0) {
                grupo[i] = 0;
                res--;
            }
        }
        grupo[op] = 0;

    }

    cout << res;
}

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