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>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
int main() {
speed;
int n,x;
cin>>n>>x;
vector<int> a(n+1);
vector<int> dp(n+1);
for (int i=1;i<=n;i++) {
cin>>a[i];
}
vector<int> curr;
for (int i=1;i<=n;i++) {
if (curr.empty() or curr.back()<a[i]) {
curr.push_back(a[i]);
dp[i]=curr.size();
} else {
auto it = lower_bound(all(curr),a[i]);
*it = a[i];
dp[i]=it-curr.begin()+1;
}
// cout<<dp[i]<<" ";
}
// cout<<"dp\n";
curr.clear();
vector<int> dp2(n+1);
for (int i=n;i>=1;i--) {
if (curr.empty() or curr.back()>a[i]-x) dp2[i]=curr.size()+1;
else {
int l=0,r=curr.size()-1;
while (l<r) {
int mid=l+r>>1;
if (curr[mid]<=a[i]-x) r=mid;
else l=mid+1;
}
dp2[i]=l+1;
}
if (curr.empty() or curr.back()>a[i]) curr.push_back(a[i]);
else {
int l=0,r=curr.size()-1;
while (l<r) {
int mid=l+r>>1;
if (curr[mid]<=a[i]) r=mid;
else l=mid+1;
}
curr[l]=a[i];
}
// cout<<dp2[i]<<" ";
}
// cout<<"dp2\n";
int ans=0;
for (int i=1;i<=n;i++) {
// cout<<dp[i]<<" "<<dp2[i]<<" dp dp2\n";
ans=max(ans,dp[i]+dp2[i]-1);
}
cout<<ans<<"\n";
return 0;
}
/*
10 10
2 34 545 56 3 3 65 2 7 6
*/
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:55:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid=l+r>>1;
| ~^~
glo.cpp:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=l+r>>1;
| ~^~
# | 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... |