oj.uz

Submission #951361

# Submission time Handle Problem Language Result Execution time Memory
951361 2024-03-21T17:15:13 Z AndreyPavlov The short shank; Redemption (BOI21_prison) C++14
0 / 100
 99 ms 67796 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);
    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) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Incorrect 4 ms 1628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 99 ms 67796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Incorrect 4 ms 1628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 20 ms 14804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Incorrect 4 ms 1628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Incorrect 4 ms 1628 KB Output isn't correct
8 Halted 0 ms 0 KB -