cjb-poi2010pilots

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 3000010
int limit,n;
int a[N];
deque<int> maxq,minq;
int main()
{
    cin>>limit>>n;
    rep(i,n)scanf("%d",&a[i]);
    int ans=1;
    int j=1;
    rep(i,n)
    {
        while (!maxq.empty() && a[i]>=a[maxq.back()])maxq.pop_back(); maxq.pb(i);
        while (!minq.empty() && a[i]<=a[minq.back()])minq.pop_back(); minq.pb(i);
        while (a[maxq.front()]-a[minq.front()]>limit)
            if (maxq.front()<minq.front())j=maxq.front()+1,maxq.pop_front();
            else j=minq.front()+1,minq.pop_front();
        ans=max(ans,i-j+1);
    }
    cout<<ans<<endl;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 3000010
int limit,n;
int a[N];
deque<int> maxq,minq;
int main()
{
    cin>>limit>>n;
    rep(i,n)scanf("%d",&a[i]);
    int ans=1;
    int j=1;
    rep(i,n)
    {
        while (!maxq.empty() && a[i]>=a[maxq.back()])maxq.pop_back(); maxq.pb(i);
        while (!minq.empty() && a[i]<=a[minq.back()])minq.pop_back(); minq.pb(i);
        while (a[maxq.front()]-a[minq.front()]>limit)
            if (maxq.front()<minq.front())j=maxq.front()+1,maxq.pop_front();
            else j=minq.front()+1,minq.pop_front();
        ans=max(ans,i-j+1);
    }
    cout<<ans<<endl;
}