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>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
long long res=1;
while (b>0){
if (b%2==1) res=(res*a)%p;
b/=2;
a=(a*a)%p;
}
return res;
}
long long n,x,arr[200001],ans[200001];
long long res;
void runtc(){
cin>>n>>x;
for (int i=1;i<=n;i++){
cin>>arr[i];
}
//can consider only decrementing
//only need consider decrement [1,x]
//try to "fix" x
//find LIS for prefix and suffix
vector<long long> lol;
for (int i=n;i>=1;i--){
int pos=lower_bound(lol.begin(),lol.end(),-(arr[i]-x))-lol.begin();
ans[i]=pos+1;
pos=lower_bound(lol.begin(),lol.end(),-(arr[i]))-lol.begin();
if (pos>=lol.size()){
lol.pb(-arr[i]);
}
else {
lol[pos]=-arr[i];
}
}
lol.clear();
for (int i=1;i<=n;i++){
int pos=lower_bound(lol.begin(),lol.end(),arr[i])-lol.begin();
if (pos>=lol.size()){
lol.pb(arr[i]);
}
else {
lol[pos]=arr[i];
}
res=max(res,(long long)pos+ans[i]);
}
cout<<res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("pcb.in","r",stdin);
// freopen("pcb.out","w",stdout);
freopen("input1.in","r",stdin);
// freopen("output1.out","w",stdout);
//freopen("tower_rush_input.txt","r",stdin);
//freopen("hackercup_output.txt","w",stdout);
int tcs;
// cin>>tcs;
tcs=1;
for (int i=1;i<=tcs;i++){
// cout<<"Case #"<<i<<": ";
runtc();
}
}
Compilation message (stderr)
glo.cpp: In function 'void runtc()':
glo.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (pos>=lol.size()){
| ~~~^~~~~~~~~~~~
glo.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if (pos>=lol.size()){
| ~~~^~~~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | freopen("input1.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |