// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(sth) sth.begin(), sth.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e18 + 7;
#define int ll
class Segment_Tree
{
private:
struct node {
int val = 0;
int Lazy = 0;
};
int n;
vector<node> Tree;
inline void Operate(int id, int l, int r) {
if (Tree[id].Lazy == 0)
return;
Tree[id].val += Tree[id].Lazy;
if (l != r) {
Tree[id << 1].Lazy += Tree[id].Lazy;
Tree[id << 1 | 1].Lazy += Tree[id].Lazy;
}
Tree[id].Lazy = 0;
}
inline void Range_Update(int id, int l, int r, int lo, int hi, int num) {
Operate(id, l, r);
if (l > hi || r < lo)
return;
else if (l >= lo && r <= hi) {
Tree[id].Lazy += num;
Operate(id, l, r);
return;
}
int mid = (l + r) >> 1;
Range_Update(id << 1, l, mid, lo, hi, num);
Range_Update(id << 1 | 1, mid + 1, r, lo, hi, num);
//
Tree[id].val = max(Tree[id << 1].val, Tree[id << 1 | 1].val);
}
inline int Get(int id, int l, int r, int lo, int hi) {
Operate(id, l, r);
//
if (l > hi || r < lo)
return -INF;
else if (l >= lo && r <= hi) {
return Tree[id].val;
}
int mid = (l + r) >> 1;
int ans1 = Get(id << 1, l, mid, lo, hi);
int ans2 = Get(id << 1 | 1, mid + 1, r, lo, hi);
//
return max(ans1, ans2);
}
public:
Segment_Tree(int len) {
//
n = len;
Tree.assign(n << 2, {0, 0});
}
void Range_Update(int l, int r, int num) {
Range_Update(1, 1, n, l, r, num);
}
int Get(int l, int r) {
return Get(1, 1, n, l, r);
}
};
void solve(){
int n, x;cin >> n >> x;
vector<int> a(n+1, 0);
for(int i=1; i<=n; ++i)cin >> a[i];
vector<int> temp;
for(int i=1; i<=n; ++i){
temp.push_back(a[i] + 1);
temp.push_back(a[i] + 1 - x);
temp.push_back(a[i]);
}
temp.push_back(INF);
sort(alle(temp));
temp.erase(unique(alle(temp)), temp.end());
auto get_pos = [&](int x){
int pos = lower_bound(alle(temp), x) - temp.begin();
return pos + 1;
};
// for(auto &elm: temp)cout << elm << ' ';
// cout << '\n';
// cout << get_pos(12);
// return;
vector<int> dp;
vector<int> lis(n+10, 0);
for(int i=1; i<=n; ++i){
int pos = lower_bound(alle(dp), a[i]) - dp.begin();
if(pos == dp.size()){
dp.push_back(a[i]);
lis[i] = pos;
}
else{
dp[pos] = a[i];
lis[i] = pos;
}
}
// for(int i=1; i<=n; ++i)cout << lis[i] << '\n';
Segment_Tree seg(temp.size() + 10);
vector<int> suff(n+10, 0);
int INFpos = get_pos(INF);
for(int i=n; i>0; --i){
suff[i] = seg.Get(get_pos(a[i] + 1 - x), INFpos);
seg.Range_Update(get_pos(a[i]), get_pos(a[i]), seg.Get(get_pos(a[i] + 1), INFpos) + 1);
}
int ans = -INF;
for(int i=1; i<=n; ++i){
ans = max(ans, lis[i] + suff[i]);
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
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... |