#include <bits/stdc++.h>
using namespace std;
int main() {
int n, num, d;
cin >> n >> d;
map<int, int> blub, fred;
blub[-d] = fred[-d] = 0;
for (int i = 0; i < n; i++) {
cin >> num;
blub[num] = prev(blub.lower_bound(num))->second + 1;
fred[num] = max(prev(blub.lower_bound(num + d))->second + 1, prev(fred.lower_bound(num))->second + 1);
auto it = blub.find(num);
int val = it->second;
auto nextit = next(it);
while(nextit != blub.end() && nextit->second < val) {
blub.erase(nextit);
nextit = next(blub.find(num));
}
{
auto it = fred.find(num);
int val = it->second;
auto nextit = next(it);
while(nextit != fred.end() && nextit->second < val) {
fred.erase(nextit);
nextit = next(fred.find(num));
}
}
}
cout << fred.rbegin()->second << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
298 ms |
2312 KB |
Output is correct |
2 |
Correct |
290 ms |
2372 KB |
Output is correct |
3 |
Correct |
293 ms |
2344 KB |
Output is correct |
4 |
Correct |
284 ms |
2444 KB |
Output is correct |
5 |
Correct |
218 ms |
10724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
68 ms |
956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
1228 KB |
Output is correct |
2 |
Correct |
133 ms |
1320 KB |
Output is correct |
3 |
Correct |
275 ms |
2244 KB |
Output is correct |
4 |
Correct |
153 ms |
6072 KB |
Output is correct |
5 |
Correct |
133 ms |
5464 KB |
Output is correct |
6 |
Correct |
277 ms |
14812 KB |
Output is correct |
7 |
Correct |
293 ms |
10984 KB |
Output is correct |
8 |
Correct |
132 ms |
4392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |