• Source 
    1. /**************************************************************
    2.     Problem: 2096
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:3036 ms
    7.     Memory:59400 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. #include<cmath>
    14. //by zrt
    15. //problem:
    16. using namespace std;
    17. typedef long long ll;
    18. const double eps(1e-10);
    19. int n,k,a[3000005];
    20. int ans;
    21. //4 5 6
    22. //3
    23. int read(){
    24.     static char x;
    25.     static int num;
    26.     while(x=getchar(),x<'0'||x>'9');
    27.     num=x-'0';
    28.     while(x=getchar(),x>='0'&&x<='9') num*=10,num+=x-'0';
    29.     return num;
    30. }
    31. struct dddl{
    32.     int q[3000005],pos[3000005],h,t;
    33.     inline void pop_front(int p){
    34.         if(pos[h]==p) h++;
    35.     }
    36.     inline void add(int x,int p){
    37.         while(h!=t&&q[t-1]>x){
    38.             t--;
    39.         }
    40.         q[t++]=x;pos[t-1]=p;
    41.     }
    42.     inline int get(){
    43.         return q[h];
    44.     }
    45. }mx,mn;
    46. int main(){
    47.     #ifdef LOCAL
    48.     freopen("in.txt","r",stdin);
    49.     freopen("out.txt","w",stdout);
    50.     #endif
    51.     k=read();n=read();
    52.     for(int i=1;i<=n;i++) a[i]=read();
    53. //  a[n+1]=a[n]-k-1;n++;
    54.     int can=0;
    55.     for(int i=1;i<=n;i++){
    56.         if(can<i){
    57.             mx.add(-a[i],i);
    58.             mn.add(a[i],i);
    59.             can++;
    60.         }
    61.         while(can<=n&& -mx.get()-(ll)mn.get()<=k) {
    62.             can++;
    63.             mx.add(-a[can],can);
    64.             mn.add(a[can],can);
    65.         }
    66.         ans=max(ans,can-i);
    67.         mx.pop_front(i);mn.pop_front(i);
    68.     }
    69.     printf("%d\n",ans);
    70.     return 0;
    71. }