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;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 4e5 + 5;
int a[mn], dp[mn];
vector<pii> cmp;
int getID (int targ, int p) {
return lower_bound(all(cmp), make_pair(targ, p)) - cmp.begin();
}
struct IT {
vector<int> tr;
IT (int sz) : tr(4 * sz) {}
void update (int pos, int val, int k, int l, int r) {
if (pos < l || r < pos) return;
if (l == r) {
tr[k] = val;
return;
}
int mid = (l + r) >> 1;
update(pos, val, 2 * k, l, mid);
update(pos, val, 2 * k + 1, mid + 1, r);
tr[k] = max(tr[2 * k], tr[2 * k + 1]);
}
int query (int a, int b, int k, int l, int r) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return tr[k];
int mid = (l + r) >> 1;
return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
}
} preTree(mn), sfxTree(mn);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, x; cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cmp.emplace_back(a[i], i);
cmp.emplace_back(a[i] - x, i);
}
sort(all(cmp)); filter(cmp);
int mx = cmp.size() - 1, ans = 0;
for (int i = n; i >= 1; i--) {
dp[i] = sfxTree.query(getID(a[i], INT_MAX), mx, 1, 0, mx) + 1;
sfxTree.update(getID(a[i], i), dp[i], 1, 0, mx);
}
for (int i = 1; i <= n; i++) {
sfxTree.update(getID(a[i], i), 0, 1, 0, mx);
dp[i] = preTree.query(0, getID(a[i] - x, 0) - 1, 1, 0, mx) + 1;
preTree.update(getID(a[i] - x, i), dp[i], 1, 0, mx);
ans = max(ans, dp[i] + sfxTree.query(getID(a[i] - x, INT_MAX), mx, 1, 0, mx));
}
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... |