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;
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 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];
a[i]+=inf;
}
cout<<max(solve(-x),solve(x))<<"\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... |