fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define data_type int
  4. class segment_tree
  5. {
  6. public:
  7.     data_type tree[4*10000][2];
  8.     vector<data_type>arr,lazy;
  9.     pair<data_type,data_type> ans;
  10.  
  11.     void build(int p,int begin,int end)
  12.     {
  13.         if(begin==end)
  14.             {
  15.                 tree[p][0]=tree[p][1]=arr[begin];
  16.                 return;
  17.             }
  18.         int left=p<<1;
  19.         int right=(p<<1)+1;
  20.         int mid=(begin+end)>>1;
  21.         build(left,begin,mid);
  22.         build(right,mid+1,end);
  23.         tree[p][0]=max(tree[left][0],tree[right][0]);
  24.         tree[p][1]=min(tree[left][1],tree[right][1]);
  25.  
  26.     }
  27.  
  28.     void print(int p, int begin, int end)
  29.     {
  30.         cout<<"--->"<<p<<" "<<begin<<" "<<end<<" {"<<tree[p][0]<<","<<tree[p][1]<<"}"<<endl;
  31.         if (begin==end)
  32.             return;
  33.         int mid = (begin+end)>>1;
  34.         print(p<<1, begin, mid);
  35.         print((p<<1)+1, mid+1, end);
  36.     }
  37.  
  38.     void query(int p,int begin,int end,int l,int r)
  39.     {
  40.         if(l>end || r<begin)
  41.             return ;
  42.         if (begin >= l && end <= r)
  43.             {
  44.                 ans= make_pair(tree[p][0],tree[p][1]);
  45.                 return ;
  46.             }
  47.  
  48.         int left=p<<1;
  49.         int right=(p<<1)+1;
  50.         int mid=(begin+end)>>1;
  51.         query(left, begin,mid,l,r);
  52.         query(right, mid+1,end,l,r);
  53.     }
  54.  
  55.     segment_tree(vector<data_type> temp)
  56.     {
  57.         arr=temp;
  58.         memset(tree,0,sizeof(tree));
  59.         build(1,1,arr.size());
  60.         print(1,1,arr.size());
  61.         // lazy.assign(4*arr.size(),0LL);
  62.     }
  63.     pair<data_type,data_type> rmq(int i,int j)
  64.     {
  65.         query(1,1,arr.size(),i,j);
  66.         return ans;
  67.     }
  68.  
  69. };
  70. int  main()
  71. {
  72.  
  73.  
  74.     int n,q,t,a,te=0;
  75.     scanf("%d",&t);
  76.     while(t--)
  77.         {
  78.             scanf("%d %d",&n,&q);
  79.  
  80.             vector<data_type> vc;
  81.             for(int i=0; i<n; i++)
  82.                 scanf("%d",&a),vc.emplace_back(a);
  83.             segment_tree st(vc);
  84.             if(q==1)
  85.                 {
  86.                     printf("0\n");
  87.                     continue;
  88.                 }
  89.             q--;
  90.             data_type  m=INT_MIN;
  91.  
  92.             for(int i=0; i<n-q; i++)
  93.                 {
  94.                     pair<data_type,data_type> p=st.rmq(i+1,i+q);
  95.                     cout<<"("<<i<<","<<i+q<<") = "<<p.first<<" "<<p.second<<endl;
  96.                     m=max(abs(p.first-p.second),m);
  97.  
  98.                 }
  99.             cout<<m<<endl;
  100.         }
  101.  
  102.     return 0;
  103.  
  104. }
  105.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
3

6 2

6 0 8 8 8 4

8 3

19 8 4 13 12 1 0 13

2 2

1 1
stdout
copy 
--->1 1 6 {49,0}
--->2 1 3 {8,0}
--->4 1 2 {8,0}
--->8 1 1 {0,0}
--->9 2 2 {8,8}
--->5 3 3 {8,8}
--->3 4 6 {49,4}
--->6 4 5 {8,4}
--->12 4 4 {8,8}
--->13 5 5 {4,4}
--->7 6 6 {49,49}
(0,1) = 0 0
(1,2) = 8 8
(2,3) = 8 8
(3,4) = 8 8
(4,5) = 4 4
0
--->1 1 8 {13,0}
--->2 1 4 {13,4}
--->4 1 2 {8,4}
--->8 1 1 {8,8}
--->9 2 2 {4,4}
--->5 3 4 {13,12}
--->10 3 3 {13,13}
--->11 4 4 {12,12}
--->3 5 8 {13,0}
--->6 5 6 {1,0}
--->12 5 5 {1,1}
--->13 6 6 {0,0}
--->7 7 8 {13,0}
--->14 7 7 {13,13}
--->15 8 8 {0,0}
(0,2) = 8 4
(1,3) = 13 13
(2,4) = 13 12
(3,5) = 1 1
(4,6) = 1 0
(5,7) = 13 13
4
--->1 1 2 {1,0}
--->2 1 1 {1,1}
--->3 2 2 {0,0}
(0,1) = 1 1
0
https://ideone.com/luFTwF
language:
C++14 (gcc 8.3)
created:
4 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!