Submission #951365

# Submission time Handle Problem Language Result Execution time Memory
951365 2024-03-21T17:26:06 Z AndreyPavlov The short shank; Redemption (BOI21_prison) C++14
0 / 100
2 ms 348 KB
#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);
    freopen("snowcow.in", "r", stdin);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Compilation message

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) {
      |                     ~~^~~~~~~~~~~~
prison.cpp: In function 'int main()':
prison.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen("snowcow.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -