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

Download