This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "
constexpr int N = 3e5 + 10;
int n, last[N], dp[N], mx[N], d, b[N];
pair<int, int> idx[N];
long long a[N];
void compress() {
static long long tmp[N];
memcpy(tmp, a, sizeof(a));
sort(tmp, tmp + n);
int m = unique(tmp, tmp + n) - tmp;
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(tmp, tmp + m, a[i]) - tmp;
}
}
int t[N << 1];
void build(int *shit) {
for (int i = 0; i < n; ++i) {
t[i + n] = shit[i];
}
for (int i = n - 1; i > 0; --i) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
void update(int i, int x) {
for (t[i += n] = x; i > 1; i >>= 1) {
t[i >> 1] = max(t[i], t[i ^ 1]);
}
}
int query(int u, int v) {
int res = 0;
for (u += n, v += n; u < v; u >>= 1, v >>= 1) {
if (u & 1) {
res = max(res, t[u++]);
}
if (v & 1) {
res = max(res, t[--v]);
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> d;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
compress();
for (int i = 0; i < n; ++i) {
idx[i] = {a[i], -i};
b[i] = a[i];
}
build(b);
for (int i = 0; i < n; ++i) {
mx[i] = query(max(0, i - d), i + 1);
}
build(mx);
for (int i = 0; i < n; ++i) {
int low = i + d + 1, high = n - 1;
while (high - low > 0) {
int mid = (high + low) >> 1;
if (query(i + d + 1, mid + 1) > a[i]) {
high = mid;
} else {
low = mid + 1;
}
}
last[i] = min(n, low);
}
sort(idx, idx + n, greater<pair<int, int>>());
fill(t, t + 2 * N, -1e9);
for (auto &_ : idx) {
int i = -_.second;
dp[i] = max(query(i + 1, last[i]), 0) + 1;
update(i, dp[i]);
}
cout << *max_element(dp, dp + 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... |