이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct node {
int l, r, val;
node *left, *right;
} *root0, *root1;
node *build(int l, int r) {
if (l == r) return new node{l, r, -INF, nullptr, nullptr};
node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
return new node{l, r, -INF, left, right};
}
int query(node *cur, int l, int r) {
if (cur->l > r || cur->r < l) return -INF;
if (l <= cur->l && cur->r <= r) return cur->val;
return max(query(cur->left, l, r), query(cur->right, l, r));
}
void update(node *cur, int idx, int v) {
if (cur->l == cur->r) {
cur->val = max(cur->val, v);
return;
}
if (idx <= cur->left->r) update(cur->left, idx, v);
else update(cur->right, idx, v);
cur->val = max(cur->left->val, cur->right->val);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, x; cin >> n >> x;
vector<int> a(n), b(n);
map<int, int> mp = {{-INF, 0}};
for (int i = 0; i < n; i++) cin >> a[i], mp[a[i]] = 0;
int cnt = 0;
for (auto &p : mp) p.second = cnt++;
for (int i = 0; i < n; i++) b[i] = mp[a[i]];
root0 = build(0, cnt - 1), root1 = build(0, cnt - 1);
update(root0, 0, 0);
for (int i = 0; i < n; i++) {
update(root1, b[i], max(query(root0, 0, prev(mp.lower_bound(a[i] + x))->second), query(root1, 0, b[i] - 1)) + 1);
update(root0, b[i], query(root0, 0, b[i] - 1) + 1);
}
cout << max(query(root0, 0, cnt - 1), query(root1, 0, cnt - 1)) << '\n';
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... |