Submission #951361

#	Time	Username	Problem	Language	Result	Execution time	Memory
951361		AndreyPavlov	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	99 ms	67796 KiB

prison

#include <bits/stdc++.h>
#define int long long

/* Using libraries */
using namespace std;

using ld = long double;
template <class T>
using vc = vector <T>;
using pii = pair <int, int>;
using pint = pair <int, int>;
template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const int N = 5e5;
const int inf = 1e9;
int a[N], t, n;

void solve() {
    int d;
    cin >> n >> d >> t;
    vc <int> st;
    vc <int> b(n), c(n);
    vc <pii> seg;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        int x = a[i] - i;
        b[i] = x;
        while (!st.empty() && b[st.back()] >= b[i])
            st.pop_back();
        st.push_back(i);
        int l = -1, r = st.size();
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (t - i <= b[st[m]]) {
                r = m;
            } else {
                l = m;
            }
        }
        if (r == 0)
            c[i] = 0;
        else
            c[i] = st[r - 1] + 1;
        if (a[i] >= t) {
            seg.push_back({c[i], i});
        }
    }
    vc <set <int>> in(n);
    for (int i = 0; i < seg.size(); ++i) {
        for (int j = seg[i].first; j <= seg[i].second; ++j)
            in[j].insert(i);
    }
    int res = n;
    for (int i = 0; i < d; ++i) {
        int k = -1, mx = 0;
        for (int j = 0; j < n; ++j) {
            if (chmax(mx, (int)in[j].size())) {
                k = j;
            }
        }
        if (k == -1)
            break;
        res -= mx;
        set <int> was = in[k];
        for (int j : was) {
            for (int w = seg[j].first; w <= seg[j].second; ++w)
                in[w].erase(j);
        }
    }
    cout << res << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

prison.cpp: In function 'void solve()':
prison.cpp:65:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < seg.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

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