#include <bits/stdc++.h>
using namespace std;
int n, x, a[200200];
vector<int> vals;
unordered_map<int, int> f;
void compress() {
for (int i=1; i<=n; i++) vals.push_back(a[i]);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i=0; i<vals.size(); i++) f[vals[i]] = i + 1;
}
int seg[800800];
#define mid (l + ((r - l ) >> 1))
#define left (id << 1)
#define right (id << 1 | 1)
const int inf = 2e9;
void update(int pos, int val, int id = 1, int l = 1, int r = n) {
if (l == r) { if (l == pos) seg[id] = val; return; }
if (pos <= mid) update(pos, val, left, l, mid);
else update(pos, val, right, mid + 1, r);
seg[id] = max(seg[left], seg[right]);
}
int get(int lo, int hi, int id = 1, int l = 1, int r = n) {
if (r < lo || l > hi) return 0;
if (lo <= l && r <= hi) return seg[id];
return max(get(lo, hi, left, l, mid), get(lo, hi, right, mid + 1, r));
}
int pre[200200], preval[200200];
signed main() {
ios_base::sync_with_stdio(0);
cin >> n >> x;
for (int i=1; i<=n; i++) cin >> a[i];
compress();
preval[0] = inf;
for (int i=1; i<=n; i++) {
int cur_best = 1 + get(1, f[a[i]] - 1);
if (cur_best >= pre[i-1]) {
if (cur_best > pre[i-1]) {
pre[i] = cur_best;
preval[i] = a[i];
} else {
pre[i] = cur_best;
preval[i] = min(a[i], preval[i-1]);
}
} else {
pre[i] = pre[i-1];
preval[i] = preval[i-1];
}
update(f[a[i]], cur_best);
}
fill(seg, seg + (4 * n) + 10, 0);
int ans = 0;
for (int i=n; i; i--) {
int idx = upper_bound(vals.begin(), vals.end(), preval[i] - x) - vals.begin() + 1;
int rightside = get(idx, n);
int cur_best = pre[i] + rightside;
ans = max(ans, cur_best);
update(f[a[i]], 1 + get(f[a[i]] + 1, n));
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |