| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1296842 | ciao_gio | The short shank; Redemption (BOI21_prison) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct Segment {
int n;
vector<array<int, 2>> t;
Segment() {}
Segment(int _n) : n(_n), t(2 * n) {}
void update(int i, int x) {
for (t[i += n] = {x, i - n}; i > 1; i /= 2) {
t[i / 2] = max(t[i], t[i ^ 1]);
}
}
void update(int i) {
for (t[i += n][0]++; i > 1; i /= 2) {
t[i / 2] = max(t[i], t[i ^ 1]);
}
}
int query(int l, int r) {
array<int, 2> ans = {-1, -1};
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) ans = max(ans, t[l++]);
if (r & 1) ans = max(ans, t[--r]);
}
return ans[1];
}
};
int infetti(int N, int D, int S, vector<int> T) {
Segment st(N);
for (int i = 0; i < N; i++) {
st.update(i, -1);
}
vector<int> dp(N, 0);
int ans = 0;
unordered_map<int, vector<int>> M;
set<int> R;
for (int i = 0; i < N; i++) {
if (T[i] <= S) {
R.insert(i);
M[i + S - T[i]].push_back(i);
for (int j: M[i]) {
R.erase(j);
}
st.update(i, 0);
}
else {
if (R.empty()) {
ans++;
}
else {
int x = *prev(R.end());
int y = st.query(x, i);
st.update(y);
dp[y]++;
}
for (int j: M[i]) {
R.erase(j);
}
}
}
sort(begin(dp), end(dp), [&] (int i, int j) { return i > j; });
for (int i = 0; i < min(N, D); i++) {
ans += dp[i];
}
return N - ans;
}