KDIFF - Trồng hoa
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <deque>
#include <stdio.h>
#include <cstdio>
using namespace std;
const long maxN = 300005;
struct e {
long x,p;
};
deque<e> ma,mi;
long a[maxN];
long rleft[maxN];
long rright[maxN];
long mleft[maxN];
long mright[maxN];
long n,k;
void init() {
scanf("%ld %ld", &n, &k);
for(long i=1; i<=n; i++) {
scanf("%ld", &a[i]);
}
}
e rec(long a, long b) {
e t;
t.p = b;
t.x = a;
return t;
}
int main()
{
init();
long j = 1;
for(long i=1; i<=n; i++) {
while ((!ma.empty())&&(ma.back().x<=a[i])) ma.pop_back();
while ((!mi.empty())&&(mi.back().x>=a[i])) mi.pop_back();
ma.push_back(rec(a[i],i));
mi.push_back(rec(a[i],i));
//printf("%d %d\n",ma.front().x,mi.front().x);
while ((ma.front().x-mi.front().x)>k) {
j++;
if (ma.front().p<j) ma.pop_front();
if (mi.front().p<j) mi.pop_front();
}
rleft[i] = i-j+1;
}
while (!ma.empty()) ma.pop_back();
j = n;
for(long i=n; i>=1; i--) {
while ((!ma.empty())&&(ma.back().x<=a[i])) ma.pop_back();
while ((!mi.empty())&&(mi.back().x>=a[i])) mi.pop_back();
ma.push_back(rec(a[i],i));
mi.push_back(rec(a[i],i));
//printf("%d %d\n",ma.front().x,mi.front().x);
while ((ma.front().x-mi.front().x)>k) {
j--;
if (ma.front().p>j) ma.pop_front();
if (mi.front().p>j) mi.pop_front();
}
rright[i] = j-i+1;
}
mleft[1] = rleft[1];
for(int i=2; i<=n; i++)
mleft[i] = max(mleft[i-1],rleft[i]);
mright[n] = rright[n];
for(int i=n-1; i>=1; i--)
mright[i] = max(mright[i+1],rright[i]);
long res=0;
for(long i=1; i<n; i++) {
res = max(res,mleft[i]+mright[i+1]);
}
printf("%ld",res);
return 0;
}