#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;
int n, x, ar[200001];
vector<int> coord;
int fwk[2][200001] = {};
inline void upd(int t, int x, int v)
{
x = prev(upper_bound(coord.begin(), coord.end(), x)) - coord.begin();
for (; x < coord.size(); x += x & (-x)) {fwk[t][x] = max(fwk[t][x], v);}
}
inline int qry(int t, int x)
{
int ret = 0;
x = prev(upper_bound(coord.begin(), coord.end(), x)) - coord.begin();
for (; x; x -= x & (-x)) {ret = max(ret, fwk[t][x]);}
return ret;
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> x;
coord.push_back(0);
for (int i = 0; i < n; i++)
{
cin >> ar[i];
coord.push_back(ar[i]);
}
sort(coord.begin(), coord.end());
coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
int res = 0;
for (int i = 0; i < n; i++)
{
int ret = qry(0, ar[i] - 1) + 1;
upd(0, ar[i], ret);
res = max(ret, res);
ret = qry(0, ar[i] + x - 1) + 1;
upd(1, ar[i], ret);
res = max(ret, res);
ret = qry(1, ar[i] - 1) + 1;
upd(1, ar[i], ret);
res = max(ret, res);
}
cout << res << "\n";
return 0;
}
Compilation message
glo.cpp: In function 'void upd(int, int, int)':
glo.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; x < coord.size(); x += x & (-x)) {fwk[t][x] = max(fwk[t][x], v);}
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
5488 KB |
Output is correct |
2 |
Correct |
239 ms |
5640 KB |
Output is correct |
3 |
Correct |
225 ms |
5616 KB |
Output is correct |
4 |
Correct |
230 ms |
5616 KB |
Output is correct |
5 |
Correct |
99 ms |
4080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
54 ms |
1792 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
3068 KB |
Output is correct |
2 |
Correct |
97 ms |
3068 KB |
Output is correct |
3 |
Correct |
207 ms |
5488 KB |
Output is correct |
4 |
Correct |
100 ms |
4080 KB |
Output is correct |
5 |
Correct |
60 ms |
2668 KB |
Output is correct |
6 |
Correct |
103 ms |
4716 KB |
Output is correct |
7 |
Correct |
115 ms |
5360 KB |
Output is correct |
8 |
Correct |
81 ms |
3060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |