| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 659403 | 600Mihnea | The short shank; Redemption (BOI21_prison) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 7;
const int INF = (int) 1e9 + 7;
int n;
int d;
int t;
int trebel[N];
bool block[N];
int ant[N];
bool valid[N];
pair<int, int> tree_min_valid[4 * N];
void st_valid(int v, int tl, int tr, int i, int x) {
if (tr < i || i < tl) {
return;
}
if (tl == tr) {
tree_min_valid[v] = {x, i};
return;
}
int tm = (tl + tr) / 2;
st_valid(2 * v, tl, tm, i, x);
st_valid(2 * v + 1, tm + 1, tr, i, x);
tree_min_valid[v] = min(tree_min_valid[2 * v], tree_min_valid[2 * v + 1]);
}
pair<int, int> get_min_valid(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return {INF, -1};
}
if (l <= tl && tr <= r) {
return tree_min_valid[v];
}
int tm = (tl + tr) / 2;
return min(get_min_valid(2 * v, tl, tm, l, r), get_min_valid(2 * v + 1, tm + 1, tr, l, r));
}
pair<int, int> tree[4 * N];
int lazy[4 * N];
void add(int v, int tl, int tr, int l, int r, int x) {
if (lazy[v]) {
tree[v].first += lazy[v];
if (tl < tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
tree[v].first += x;
if (tl < tr) {
lazy[2 * v] += x;
lazy[2 * v + 1] += x;
}
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, x);
add(2 * v + 1, tm + 1, tr, l, r, x);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = {0, tl};
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (int i = 0; i < 4 * N; i++) {
tree_min_valid[i] = {INF, -1};
}
cin >> n >> d >> t;
for (int i = 1; i <= n; i++) {
cin >> trebel[i];
}
build(1, 1, n - 1);
vector<int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && trebel[stk.back()] - stk.back() >= trebel[i] - i) {
stk.pop_back();
}
stk.push_back(i);
int L = 0, R = (int) stk.size() - 1;
while (L <= R) {
int mid = (L + R) / 2;
int j = stk[mid];
if (trebel[j] + i - j <= t) {
ant[i] = j;
L = mid + 1;
} else {
R = mid - 1;
}
}
}
for (int i = 1; i <= n; i++) {
valid[i] = (ant[i] > 0);
if (valid[i]) {
st_valid(1, 1, n, i, ant[i]);
}
}
for (int j = 1; j <= n; j++) {
if (valid[j]) {
add(1, 1, n - 1, ant[j], j, +1);
}
}
for (int iqd = 1; iqd <= d; iqd++) {
int jj = tree[1].second;
add(1, 1, n - 1, jj, jj, -(int) 1e9);
block[jj] = 1;
while (1) {
auto it = get_min_valid(1, 1, n, jj + 1, n);
int j = it.second;
if (it.first <= jj) {
valid[j] = 0;
if (ant[j] <= j - 1) {
add(1, 1, n - 1, ant[j], j - 1, -1);
}
st_valid(1, 1, n, j, INF);
} else {
break;
}
}
}
int sol = 0;
for (int i = 1; i <= n; i++) {
sol += valid[i];
}
cout << sol << "\n";
return 0;
}