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;
const int N=2e5+5;
int n;
int d;
vector<int>a(N);
vector<int>F(N);
struct seg{
int t[4*N];
int query(int v,int tl,int tr,int l,int r){
if(tl>=l&&tr<=r)return t[v];
if(tl>r||tr<l)return 0;
int tm=(tl+tr)/2;
return max(query(v*2,tl,tm,l,r),query(v*2+1,tm+1,tr,l,r));
}
int query(int l,int r){return query(1,1,n,l,r);}
void update(int v,int tl,int tr,int index,int value){
if(tl==tr){
t[v]=value;
return;
}
int tm=(tl+tr)/2;
if(index<=tm)update(v*2,tl,tm,index,value);
else update(v*2+1,tm+1,tr,index,value);
t[v]=max(t[v*2],t[v*2+1]);
}
void update(int i,int v){update(1,1,n,i,v);}
}seg;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>d;
for(int i=1;i<=n;i++)cin>>a[i];
F=a;
vector<int>kompres;
for(int i=1;i<=n;i++)kompres.push_back(a[i]);
sort(kompres.begin(),kompres.end());
for(int i=1;i<=n;i++)a[i]=lower_bound(kompres.begin(),kompres.end(),a[i])-kompres.begin()+1;
int lis[n+1];
for(int i=0;i<=n;i++)lis[i]=1;
for(int i=1;i<=n;i++){
lis[i]=seg.query(0,a[i]-1)+1;
seg.update(a[i],lis[i]);
}
for(int i=1;i<=n;i++)seg.update(a[i],0);
int suflis[n+1];
for(int i=0;i<=n;i++)suflis[i]=1;
for(int i=n;i>=1;i--){
suflis[i]=seg.query(a[i]+1,n)+1;
seg.update(a[i],suflis[i]);
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,suflis[i]);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(abs(F[i]-F[j])<d){
ans=max(ans,lis[i]+suflis[j]);
}
}
}
cout<<ans;
}
# | 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... |