This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5;
int n, x, a[maxn], dp[maxn];
multiset <int> fen[maxn];
vector <int> vec1, vec2;
void upd(int i, int x, int t) {
for (i++; i <= vec1.size(); i += i&(-i)) {
if (t == 1) fen[i-1].insert(x);
else fen[i-1].erase(fen[i-1].find(x));
}
}
int get(int i) {
int ans = 0;
for (i++; i; i -= i&(-i)) {
if (fen[i-1].size()) smax(ans, *fen[i-1].rbegin());
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> a[i];
vec1.pb(a[i]);
}
// a[n] = inf; vec1.pb(inf);
sort(all(vec1)); vec1.resize(unique(all(vec1))-vec1.begin());
for (int i = 0; i < n; i++) {
int j = lower_bound(all(vec2), a[i])-vec2.begin();
if (j == vec2.size()) {
vec2.pb(a[i]);
dp[i] = vec2.size();
}
else {
vec2[j] = a[i];
dp[i] = j+1;
}
j = lower_bound(all(vec1), a[i])-vec1.begin();
upd(j, dp[i], 1);
}
vec2.clear();
int ans = 0;
for (int i = n-1; i >= 0; i--) {
int res;
int j = lower_bound(all(vec2), -a[i])-vec2.begin();
if (j == vec2.size()) {
vec2.pb(-a[i]);
res = vec2.size();
}
else {
vec2[j] = -a[i];
res = j+1;
}
j = lower_bound(all(vec1), a[i])-vec1.begin();
upd(j, dp[i], -1);
j = lower_bound(all(vec1), a[i]+x)-vec1.begin();
smax(ans, get(j-1)+res);
// cout << i << ' ' << res << ' ' << get(j-1) << '\n';
// cout << get(j-1)+res << '\n';
}
cout << ans << '\n';
return 0;
}
Compilation message (stderr)
glo.cpp: In function 'void upd(int, int, int)':
glo.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (i++; i <= vec1.size(); i += i&(-i)) {
| ~~^~~~~~~~~~~~~~
glo.cpp: In function 'int32_t main()':
glo.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if (j == vec2.size()) {
| ~~^~~~~~~~~~~~~~
glo.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (j == vec2.size()) {
| ~~^~~~~~~~~~~~~~
# | 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... |