이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5, MAX_LOG_ARR = 30 + 2, MAX_ARR = 1e9;
int n, x;
int arr[MAX_N];
int l_dp[MAX_N], r_dp[MAX_N];
int segtree[MAX_N * MAX_LOG_ARR]; // Test
int n_nodes;
int l_child[MAX_N * MAX_LOG_ARR], r_child[MAX_N * MAX_LOG_ARR];
void init() {
for (int i = 1; i <= n_nodes; i++) {
segtree[i] = 0;
l_child[i] = r_child[i] = 0;
}
n_nodes = 1;
}
void propogate(int u) {
if (l_child[u]) return;
n_nodes++;
l_child[u] = n_nodes;
n_nodes++;
r_child[u] = n_nodes;
}
void update(int i, int val, int u = 1, int lo = 0, int hi = MAX_ARR) {
if (lo == hi) {
segtree[u] = val;
return;
}
propogate(u);
int mid = (lo + hi) / 2;
if (i <= mid) update(i, val, l_child[u], lo, mid);
else update(i, val, r_child[u], mid + 1, hi);
segtree[u] = max(segtree[l_child[u]], segtree[r_child[u]]);
}
int query(int l, int r, int u = 1, int lo = 0, int hi = MAX_ARR) {
if (l <= lo && hi <= r)
return segtree[u];
propogate(u);
int mid = (lo + hi) / 2, ans = 0;
if (l <= mid) ans = max(ans, query(l, r, l_child[u], lo, mid));
if (r > mid) ans = max(ans, query(l, r, r_child[u], mid + 1, hi));
return ans;
}
int main() {
// freopen("global.in", "r", stdin);
cin >> n >> x;
for (int i = 1; i <= n; i++)
cin >> arr[i];
init();
for (int i = 1; i <= n; i++) {
l_dp[i] = query(0, arr[i] - 1) + 1;
update(arr[i], l_dp[i]);
}
init();
for (int i = n; i >= 1; i--) {
r_dp[i] = query(max(arr[i] - x + 1, 1), MAX_ARR);
update(arr[i], query(arr[i] + 1, MAX_ARR) + 1);
}
// for (int i = 1; i <= n; i++) {
// cout << i << ": " << l_dp[i] << " " << r_dp[i] << endl;
// }
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, l_dp[i] + r_dp[i]);
cout << ans << '\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |