KDIFF - Trồng hoa
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 300300
using namespace std;
int n,k,re=1,a[N],f[N],g[N],Min[N],Max[N],posMin[N],posMax[N];
int lMin,rMin,lMax,rMax,newposMin[N],newposMax[N];
void updateMin(int val,int pos)
{
if (val>Min[rMin])
{
Min[++rMin]=val; posMin[rMin]=newposMin[rMax]=pos;
return;
}
while (rMin>=lMin && val<=Min[rMin]) rMin--;
if (rMin<lMin || val>Min[rMin])
{
Min[++rMin]=val; newposMin[rMin]=pos;
}
}
void updateMax(int val,int pos)
{
if (val<Max[rMax])
{
Max[++rMax]=val; posMax[rMax]=newposMax[rMax]=pos;
return;
}
while (rMax>=lMax && val>=Max[rMax]) rMax--;
if (rMax<lMax || val<Max[rMax])
{
Max[++rMax]=val; newposMax[rMax]=pos;
}
}
void calc(int f[])
{
memset(Min,0,sizeof(Min));
memset(posMin,0,sizeof(posMin));
memset(Max,0,sizeof(Max));
memset(posMax,0,sizeof(posMax));
Min[lMin=rMin=1]=a[0]; posMin[1]=newposMin[1]=0;
Max[lMax=rMax=1]=a[0]; posMax[1]=newposMax[1]=0;
f[0]=0;
for (int i=1;i<n;i++)
{
updateMin(a[i],i);
updateMax(a[i],i);
int ok=1;
while (Max[lMax]-Min[lMin]>k)
{
ok=0;
if (newposMax[lMax]<newposMin[lMin]) lMax++;
else lMin++;
}
f[i]=max(posMax[lMax],posMin[lMin]);
}
for (int i=0;i<n;i++) f[i]=max(i-f[i]+1,(i?f[i-1]:0));
}
int main()
{
cin >> n >> k;
for (int i=0;i<n;i++) scanf("%d",&a[i]);
calc(f);
reverse(a,a+n);
calc(g);
reverse(g,g+n);
for (int i=0;i<n-1;i++) re=max(re,f[i]+g[i+1]);
cout << re << endl;
return 0;
}