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>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
using ll = long long;
const int N = 200'000 + 10;
struct FenWick {
int n_node = 0;
vector<int> tree = {};
void resize(int n) { n_node = n; tree.resize(n + 10, 0); }
FenWick() {};
FenWick(int n) { this -> resize(n); };
void Update(int idx, int val) {
for( ; idx <= n_node; idx += (idx & - idx)) tree[idx] = max(tree[idx], val);
return;
}
int Query(int idx) {
int res = 0;
for( ; idx > 0; idx -= (idx & - idx)) res = max(res, tree[idx]);
return res;
}
void reset(int idx) {
for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] = 0;
return;
}
};
int n, x;
int a[N];
int b[4][N];
int prf[N][2];
int res;
void compress() {
vector<int> Pos = {};
for (int i = 1; i <= n; ++ i) {
Pos.push_back(b[0][i]);
Pos.push_back(b[1][i]);
Pos.push_back(b[2][i]);
Pos.push_back(b[3][i]);
}
sort(Pos.begin(), Pos.end());
Pos.resize(unique(Pos.begin(), Pos.end()) - Pos.begin());
for (int i = 1; i <= n; ++ i) {
b[0][i] = lower_bound(Pos.begin(), Pos.end(), b[0][i]) - Pos.begin() + 1;
b[1][i] = lower_bound(Pos.begin(), Pos.end(), b[1][i]) - Pos.begin() + 1;
b[2][i] = lower_bound(Pos.begin(), Pos.end(), b[2][i]) - Pos.begin() + 1;
b[3][i] = lower_bound(Pos.begin(), Pos.end(), b[3][i]) - Pos.begin() + 1;
}
}
void solve() {
for (int i = 1; i <= n; ++ i) {
b[0][i] = a[i];
b[1][i] = a[i] - x;
b[2][i] = -b[0][i];
b[3][i] = -b[1][i];
}
compress();
FenWick bit[2];
for (int i = 0; i < 2; ++ i) {
bit[i] = FenWick(4 * n);
}
for (int i = 1; i <= n; ++ i) {
int val[2] = {b[0][i], b[1][i]};
prf[i][0] = bit[0].Query(val[0]);
bit[0].Update(val[0] + 1, prf[i][0] + 1);
prf[i][0] = max(prf[i][0], bit[1].Query(val[0]));
prf[i][1] = bit[1].Query(val[1]);
bit[1].Update(val[1] + 1, prf[i][1] + 1);
}
for (int i = 1; i <= n; ++ i) bit[0].reset(b[0][i] + 1);
for (int i = n; i >= 1; -- i) {
int best[2] = {bit[0].Query(b[2][i]), bit[0].Query(b[3][i])};
res = max(res, best[0] + prf[i][0] + 1);
res = max(res, best[1] + prf[i][1] + 1);
bit[0].Update(b[2][i] + 1, best[0] + 1);
}
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
cin >> n >> x;
for (int i = 1; i <= n; ++ i) cin >> a[i];
solve();
reverse(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++ i) a[i] = -a[i];
solve();
cout << res;
return (0 ^ 0);
}
/// Code by vuavisao
# | 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... |