이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, x;
cin >> n >> x;
vector<int> a(n);
vector<int> dp1, dp2;
vector<vector<int>> prev(n);
vector<int> where(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = n - 1; i >= 0; --i) {
int l = 0, r = (int) dp2.size() - 1;
int idx = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (dp2[mid] > a[i]) {
l = mid + 1;
} else if (dp2[mid] < a[i]) {
r = mid - 1;
idx = mid;
} else {
idx = mid;
break;
}
}
if (idx == -1) {
dp2.push_back(-1);
idx = dp2.size() - 1;
}
where[i] = idx;
prev[idx].push_back(a[i]);
dp2[idx] = a[i];
}
int ans = -1;
for (int i = 0; i < n; ++i) {
int loc = where[i];
prev[loc].pop_back();
if (prev[loc].empty()) {
dp2.pop_back();
} else {
dp2[loc] = prev[loc].back();
}
auto it = lower_bound(dp1.begin(), dp1.end(), a[i] - x);
if (it == dp1.end()) {
dp1.push_back(a[i] - x);
} else {
*it = a[i] - x;
}
int l = 0, r = (int) dp2.size() - 1;
int idx = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (dp2[mid] > dp1.back()) {
idx = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans = max(ans, (int) dp1.size() + idx + 1);
}
cout << max(ans, (int) dp1.size());
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
# | 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... |