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;
}

Download