#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 2e6;
int n, d, t, a[N], b[N], laz[N*4];
vector<int> add[N], rem[N];
deque<int> seg[N*4];
void build(int p=1, int l=0, int r=n-1) {
if (l == r) {
if (b[l] != n) seg[p].push_back(b[l]);
return;
}
int mid = (l+r)/2;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
seg[p].resize(seg[p*2].size() + seg[p*2+1].size());
merge(all(seg[p*2]), all(seg[p*2+1]), seg[p].begin());
}
void update(int x, int p=1, int l=0, int r=n-1) {
if (l > x) {
laz[p] = max(laz[p], x);
return;
}
int mid = (l+r)/2;
if (mid > x) update(x, p*2, l, mid);
if (r > x) update(x, p*2+1, mid+1, r);
}
int query(int x, int p=1, int l=0, int r=n-1) {
if (l > x) {
while (!seg[p].empty() && seg[p].front() <= laz[p]) seg[p].pop_front();
return upper_bound(all(seg[p]), x) - seg[p].begin();
}
int mid = (l+r)/2;
int y = 0;
if (mid > x) y += query(x, p*2, l, mid);
if (r > x) y += query(x, p*2+1, mid+1, r);
return y;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> d >> t;
memset(laz, -1, sizeof(laz));
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] > t) continue;
add[i].push_back(i);
rem[min(n, i + t-a[i] + 1)].push_back(i);
}
set<int> st;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int& j : add[i]) st.insert(j);
for (int& j : rem[i]) st.erase(j);
if (a[i] <= t) {
b[i] = n;
continue;
}
if (st.empty()) {
ans++;
}
else b[i] = *prev(st.end());
}
build(); // build con b[i]
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++) {
int x = query(i); // numeros <= i a partir de i+1
//cerr << b[i] << " " << x << " ";
pq.push(make_pair(x, -i));
}//cerr << endl;
while (d && !pq.empty()) {
int x = pq.top().first;
int i = -pq.top().second;
pq.pop();
int nwX = query(i); // numeros <= i a partir de i+1
if (nwX != x) {
pq.push(make_pair(nwX, -i));
continue;
}
ans += x;
d--;
update(i); // eliminar numeros <= i a partir de i+1
}
cout << n - ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
188 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
170 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
188 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
172 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
188 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
188 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |