#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+6;
int n, d, t, a[N], b[N];
vector<int> add[N], rem[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> d >> t;
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);
}
int ans = 0;
multiset<int> st;
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] = -1;
continue;
}
if (st.empty()) {
b[i] = -1;
ans++;
}
else b[i] = *prev(st.end());
}
int mx = 0;
st.clear();
for (int i = n-1; i >= 0; i--) {
while (!st.empty() && *prev(st.end()) > i) {
st.erase(prev(st.end()));
}
int sz = st.size();
mx = max(mx, sz);
if (b[i] != -1) st.insert(b[i]);
}
cout << n - ans - mx << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
97080 KB |
Output is correct |
2 |
Incorrect |
20 ms |
96860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
96860 KB |
Output is correct |
2 |
Correct |
162 ms |
120264 KB |
Output is correct |
3 |
Correct |
160 ms |
128184 KB |
Output is correct |
4 |
Correct |
128 ms |
118992 KB |
Output is correct |
5 |
Correct |
101 ms |
110044 KB |
Output is correct |
6 |
Correct |
92 ms |
109436 KB |
Output is correct |
7 |
Correct |
164 ms |
124460 KB |
Output is correct |
8 |
Correct |
112 ms |
111444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
97080 KB |
Output is correct |
2 |
Incorrect |
20 ms |
96860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
96860 KB |
Output is correct |
2 |
Incorrect |
34 ms |
99420 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
97080 KB |
Output is correct |
2 |
Incorrect |
20 ms |
96860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
97080 KB |
Output is correct |
2 |
Incorrect |
20 ms |
96860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |