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 MAXN 200007
using namespace std;
const int inf=1e9;
struct ST{
struct node{
int l,r,val;
};
node tree[30*MAXN];
int num;
void init(){
num=1;
tree[num]={0,0,0};
}
void addnode(){
num++;
tree[num]={0,0,0};
}
void check(int v){
if(tree[v].l==0){
addnode(); tree[v].l=num;
}
if(tree[v].r==0){
addnode(); tree[v].r=num;
}
}
void update(int v,long long l,long long r,int pos,int val){
if(l==r){
tree[v].val=max(tree[v].val,val);
}else{
long long tt=(l+r)/2;
check(v);
if(pos<=tt)update(tree[v].l,l,tt,pos,val);
else update(tree[v].r,tt+1,r,pos,val);
tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val);
}
}
int getmax(int v,long long l,long long r,long long ll,long long rr){
if(ll>rr or v==0)return 0;
if(l==ll and r==rr){
return tree[v].val;
}else{
long long tt=(l+r)/2;
return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
}
}
}seg[3];
int n,a[MAXN],ans,x,b[MAXN];
int dp[MAXN][3];
int solve(int d){
seg[0].init();
seg[1].init();
seg[2].init();
int res=0;
for(int i=1;i<=n;i++){
dp[i][0]=seg[0].getmax(1,0,2*inf,0,a[i]-1)+1;
dp[i][1]=max(seg[1].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[0].getmax(1,0,2*inf,0,a[i]+d-1)+1);
dp[i][2]=max(seg[2].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[1].getmax(1,0,2*inf,0,a[i]-d-1)+1);
seg[0].update(1,0,2*inf,a[i],dp[i][0]);
seg[1].update(1,0,2*inf,a[i],dp[i][1]);
seg[2].update(1,0,2*inf,a[i],dp[i][2]);
res=max(res,max(dp[i][0],max(dp[i][1],dp[i][2])));
}
return res;
}
int sol[2000007],pos;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
long long l=-x,r=x,lt,rt;
while(l+20<r){
lt=l+(r-l+1)/3;
rt=r-(r-l+1)/3;
int ls=solve(lt);
int rs=solve(rt);
if(ls>rs)l=lt;
else if(rs>ls)r=rt;
else break;
}
sort(b+1,b+n+1);
vector<int> w={0};
for(int i=1;i<=n;i++){
for(int f=i+1;f<=n;f++){
if(b[i]-b[f]+1>=-x and b[i]-b[f]+1<=x){
w.push_back(b[i]-b[f]+1);
}else break;
}
for(int f=i-1;f>=1;f--){
if(b[i]-b[f]+1>=-x and b[i]-b[f]+1<=x){
w.push_back(b[i]-b[f]+1);
}else break;
}
for(int f=i+1;f<=n;f++){
if(b[i]-b[f]-1>=-x and b[i]-b[f]-1<=x){
w.push_back(b[i]-b[f]-1);
}else break;
}
for(int f=i-1;f>=1;f--){
if(b[i]-b[f]-1>=-x and b[i]-b[f]-1<=x){
w.push_back(b[i]-b[f]-1);
}else break;
}
}
for(int d:w){
ans=max(ans,solve(d));
}
cout<<ans<<"\n";
return 0;
}
# | 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... |