fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4.  
  5. #define RMQ 1,0,n2-1
  6.  
  7. using namespace std;
  8. int maxt[2000010];
  9. int mint[2000010];
  10. int n2;
  11. int n,l;
  12. void sn2()
  13. {
  14.     int two=1;
  15.     while(two<n)
  16.         two*=2;
  17.     n2=two;
  18. }
  19. void build(int i)
  20. {
  21.     if(i>=n2)
  22.     {
  23.         if(i-n2>=n)
  24.         {
  25.             maxt[i]=-10000000;
  26.             mint[i]=10000000;
  27.         }
  28.         return;
  29.     }
  30.     build(i*2);
  31.     build(i*2+1);
  32.     maxt[i]=max(maxt[i*2],maxt[i*2+1]);
  33.     mint[i]=min(mint[i*2],mint[i*2+1]);
  34. }
  35. int findMax(int l,int r,int i,int L,int R)
  36. {
  37.     int mid=(L+R)/2;
  38.     if(L==l && R==r)
  39.     {
  40.         return maxt[i];
  41.     }
  42.     if(r<=mid)
  43.     {
  44.         return findMax(l,r,i*2,L,mid);
  45.     }
  46.     else if(l>mid)
  47.     {
  48.         return findMax(l,r,i*2+1,mid+1,R);
  49.     }
  50.     else
  51.     {
  52.         return max( findMax(l,mid,i*2,L,mid) ,
  53.                     findMax(mid+1,r,i*2+1,mid+1,R) );
  54.     }
  55. }
  56. int findMin(int l,int r,int i,int L,int R)
  57. {
  58.     int mid=(L+R)/2;
  59.     if(L==l && R==r)
  60.     {
  61.         return mint[i];
  62.     }
  63.     if(r<=mid)
  64.     {
  65.         return findMin(l,r,i*2,L,mid);
  66.     }
  67.     else if(l>mid)
  68.     {
  69.         return findMin(l,r,i*2+1,mid+1,R);
  70.     }
  71.     else
  72.     {
  73.         return min( findMin(l,mid,i*2,L,mid) ,
  74.                     findMin(mid+1,r,i*2+1,mid+1,R) );
  75.     }
  76. }
  77. int main()
  78. {
  79.     while(~scanf("%d %d",&n,&l),n!=0||l!=0)
  80.     {
  81.         if(l>=n)l=n-1;
  82.         sn2();
  83.         for(int i=0;i<n;i++)
  84.         {
  85.             int a;
  86.             scanf("%d",&a);
  87.             maxt[n2+i]=mint[n2+i]=a;
  88.         }
  89.         build(1);
  90.         int ans=0;
  91.         for(int i=0;i+l<n;i++)
  92.         {
  93.             ans=max(ans , findMax(i,i+l,RMQ)-findMin(i,i+l,RMQ));
  94.         }
  95.         printf("%d\n",ans);
  96.     }
  97. }
  98.  
Success #stdin #stdout 0s 18976KB
comments (?)
stdin
copy 
6 2
1 8 -1 10 7 4
5 3
-4 1 5 2 6
0 0
stdout
copy 
11
9
https://ideone.com/7pY8XQ
http://f...content-available-to-author-only...s.org/thread-556-1-1.html
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!