#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 1;
struct stree {
#define lc v*2
#define rc v*2+1
vector <int> tree;
stree (int s) {
tree.resize(s*4, 0);
}
void pushup(int v) {
tree[v] = max(tree[lc], tree[rc]);
}
void update(int v, int tl, int tr, int p, int val) {
if (tl > p || tr < p)
return;
if (tl == tr) {
tree[v] = val;
return;
}
int tm = (tl + tr) / 2;
update(lc, tl, tm, p, val);
update(rc, tm+1, tr, p, val);
pushup(v);
}
int query(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return -1;
if (tl >= l && tr <= r)
return tree[v];
int tm = (tl + tr) / 2;
int a = query(lc, tl, tm, l, r);
int b = query(rc, tm+1, tr, l, r);
return max(a, b);
}
};
bool comp(pair <int, int> a, pair <int, int> b) {
if (a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
int last[maxn];
int head(int x) {
if (x == last[x])
return x;
return last[x] = head(last[x]);
}
void connect(int a, int b) {
a = head(a);
b = head(b);
if (a != b) {
if (a > b)
swap(a, b);
last[b] = a;
}
}
int main() {
int n, d;
cin >> n >> d;
vector <pair <int, int>> nums(n);
for (int i = 0; i < n; i++) {
last[i] = i;
cin >> nums[i].first;
nums[i].second = i;
}
sort(nums.begin(), nums.end(), comp);
vector <int> dp(n);
stree tree(n);
set <int> ids;
for (int i = 0; i < n; i++) {
int id = nums[i].second;
auto it = ids.upper_bound(id);
if (it != ids.end()) {
if (*it - id <= d)
connect(*it, id);
}
if (it != ids.begin()) {
it--;
if (id - *it <= d)
connect(*it, id);
}
int st = head(id);
dp[id] = tree.query(1, 0, n, st, id) + 1;
tree.update(1, 0, n, id, dp[id]);
ids.insert(id);
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
# | 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... |